Signal representations with minimum ℓ-norm

Christoph Studer, Wotao Yin, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations

Abstract

Maximum (or ℓ) norm minimization subject to an underdetermined system of linear equations finds use in a large number of practical applications, such as vector quantization, peak-to-average power ratio (PAPR) (or 'crest factor') reduction in wireless communication systems, approximate neighbor search, robotics, and control. In this paper, we analyze the fundamental properties of signal representations with minimum ℓ-norm. In particular, we develop bounds on the maximum magnitude of such representations using the uncertainty principle (UP) introduced by Lyubarskii and Vershynin, 2010, and we characterize the limits of ℓ-norm-based PAPR reduction. Our results show that matrices satisfying the UP, such as randomly subsampled Fourier or i.i.d. Gaussian matrices, enable the efficient computation of so-called democratic representations, which have both provably small ℓ-norm and low PAPR.

Original languageEnglish (US)
Title of host publication2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012
Pages1270-1277
Number of pages8
DOIs
StatePublished - 2012
Event2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012 - Monticello, IL, United States
Duration: Oct 1 2012Oct 5 2012

Publication series

Name2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012

Other

Other2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012
CountryUnited States
CityMonticello, IL
Period10/1/1210/5/12

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Signal representations with minimum ℓ<sub>∞</sub>-norm'. Together they form a unique fingerprint.

Cite this