  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,
approximate nearest neighbor search, peak-to-average power ratio (or "crest
factor") reduction in communication systems, and peak force minimization in
robotics and control. 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, and study
the efficacy of $\ell_{\infty}$-norm-based dynamic range 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 dynamic range. 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 dynamic range reduction in a DVB-T2-based broadcast system.
