Friday, January 17, 2014

Democratic Representations

You probably recall an implementation of an l_infinity solver back in 2011, there are now two new algorithms to perform those reconstructions. No word yet on where they are located. Let us note the effective appearance of a new kind of sharp phase transition with a democratic proxy on the y-axis and the fact that it opens the door to other empirical approaches investigating other norms and attendant of signals/phase transitions. Without further due, here is the paper:

Democratic Representations by Christoph Studer, Tom Goldstein, Wotao Yin, Richard G. 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. 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.
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: