Democratic representations

Christoph Studer, Tom Goldstein, Wotao Yin, and Richard Baraniuk



Minimization of the ell_infty (or maximum) norm subject to a constraint that imposes consistency to an underdetermined system of linear equations finds use in a large number of practical applications, including vector quantization, peak-to-average power ratio (PAPR) (or “crest factor”) reduction in communication systems, approximate nearest neighbor search, and peak force minimization in robotics and control.

The plots below compare three different representations of a signal with minimal ell_infty (democratic), ell_2 (least-squares), and ell_1 (sparse) norms. The democratic representation has the smallest dynamic range and peak-to-average power ratio.


This paper

This paper analyzes the fundamental properties of signal representations obtained by solving such a convex optimization problem. We develop bounds on the maximum magnitude of such representations using the uncertainty principle (UP) introduced by Lyubarskii and Vershynin, IEEE Trans. IT, 2010, and study the efficacy of ell_infty-norm-based PAPR reduction. Our analysis shows that matrices satisfying the UP, such as randomly subsampled Fourier or i.i.d. Gaussian matrices, enable the computation of what we call democratic representations, whose entries all have small and similar magnitude, as well as low PAPR. To compute democratic representations at low computational complexity, we present two new, efficient convex optimization algorithms. We finally demonstrate the efficacy of democratic representations for PAPR reduction in a DVB-T2-based broadcast system.


C. Studer, T. Goldstein, W. Yin, and R. Baraniuk, Democratic representations, arXiv:1401.3420.

« Back