Democratic Representations

Christoph Studer, Tom Goldstein, Wotao Yin, Richard G. BaraniukarXiv 2014 · arXiv

Abstract

This research explores "democratic representations"—signal representations where every entry has a small and similar magnitude, effectively spreading energy evenly across all components. By minimizing the $\ell_\infty$-norm subject to linear constraints, the authors provide a theoretical framework and efficient algorithms to significantly reduce the Peak-to-Average Power Ratio (PAPR) in communication systems like DVB-T2.

Introduction

In many fields—ranging from wireless communications to robotics—the "dynamic range" of a signal is a major bottleneck. In Orthogonal Frequency Division Multiplexing (OFDM), which powers modern Wi-Fi and digital TV, signals often exhibit high "peaks" relative to their average power. These peaks require expensive and power-inefficient hardware, such as linear power amplifiers, to avoid signal distortion.

While researchers often seek sparse representations (where most entries are zero), this paper tackles the opposite: anti-sparse or democratic representations. The goal is to find a way to represent a signal such that no single entry "sticks out." The challenge lies in proving that such representations exist for practical matrices and developing algorithms fast enough to compute them in real-time systems.

Methodology

The authors frame the search for democratic representations as a convex optimization problem: minimize the $\ell_\infty$-norm (the maximum absolute value of any entry) of a vector $\mathbf{x}$ such that it remains consistent with the original signal $\mathbf{y}$ through a dictionary or "frame" $\mathbf{D}$.

Key Algorithms

  1. CRAM (Convex Reduction of Amplitudes): A new algorithm based on the adaptive primal-dual hybrid gradient (PDHG) scheme, designed to solve the $\ell_\infty$ minimization problem for arbitrary matrices.
  2. CRAMP (CRAM for Parseval frames): A specialized, high-speed version for Parseval frames (where matrix rows are orthonormal). It uses Douglas-Rachford splitting and ensures every intermediate step is a valid representation, which is critical for real-time hardware with strict timing budgets.
Comparison of democratic (a), least-squares (b), and sparse (c) representations. The democratic representation exhibits the flattest amplitude profile.

Key Insights and Theoretical Bounds

Using the Uncertainty Principle (UP) for frames, the authors derive new bounds on how "flat" these representations can be. They show that matrices commonly used in Compressed Sensing (like Gaussian or subsampled Fourier matrices) are also ideal for "democracy."

A central finding is the "Democracy" Lemma: for "full-spark" frames, every optimal solution to the $\ell_\infty$ problem will have at least $N - M + 1$ entries exactly equal to the maximum magnitude. This ensures the solution is naturally "flat" by design. Furthermore, by analyzing the Lagrange dual, the authors were able to tighten previous theoretical bounds on the maximum magnitude of these representations.

Experimental Results

The performance was evaluated using synthetic matrices (Gaussian, subsampled DCT) and a DVB-T2 simulation using 32,768 OFDM tones and 256-QAM modulation.

  • PAPR Reduction: In the DVB-T2 simulation, the proposed CRAMP algorithm reduced the PAPR by approximately 4.5 dB compared to a standard OFDM signal.
  • Performance vs. Standards: This approach outperformed the existing PAPR-reduction algorithm specified in the DVB-T2 standard by about 3 dB.
  • Phase Transitions: Numerical experiments revealed sharp "phase transitions" in democracy constants, showing that Parseval frames consistently yield flatter representations than non-tight frames like Gaussian matrices.

Conclusion and Future Work

While democratic representations offer significant gains in PAPR reduction, challenges remain. The computational complexity of CRAMP, though efficient, is higher than current heuristic methods used in low-cost hardware. Additionally, spreading energy "democratically" can sometimes increase total transmit power compared to a standard least-squares solution.

Future research will focus on developing specialized VLSI architectures to implement these algorithms at the gigabit-per-second speeds required by modern wireless standards and providing analytical characterizations for the observed sharp phase transitions.

Summary updated

Abstract

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.
BibTeX
@misc{studer2014democratic,
  author = {Christoph Studer and Tom Goldstein and Wotao Yin and Richard G. Baraniuk},
  title = {{Democratic Representations}},
  year = {2014},
  eprint = {1401.3420},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.3420},
}
Figure