Signal representations with minimum ℓ<inf>∞</inf>-norm

Abstract

Maximum (or ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> ) 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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> -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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> -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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sub> -norm and low PAPR.