A Low Complexity Solver ?

When Sergey Ten mentioned the paper on Anti-sparse coding for approximate nearest neighbor search by Hervé Jégou, Teddy Furon , Jean-Jacques Fuchs. I remembered the presentation entitled Uncertainty Principles, Frames, and Quantization by Roman Vershynin and Yurii Lyubarskii (The attendant paper is Uncertainty principles and vector quantization with its attendant commentary ). The element I used during our conversation is extracted from the following sentence of the paper:

The penalization in ||x||_∞ limits the range of the coefficients which in turn tend to ‘stick’ their value to ±||x||_∞ [9].

....We will provide a Matlab package to reproduce the analysis comparisons reported in this paper.

.....[9] J-J. Fuchs, “Spread representations,” in ASILOMAR Conference on Signals, Systems, and Computers, November 2011.

Since then, Hervé made the L_infinity solver of Jean-Jacques Fuchs available here. What is curious is that the solution extracted through the l_infty regularization could be made a low complexity one if a second regularizer like the TV norm were to applied during the reconstruction stage. The idea is that according to [9] the number of elements different from ±||x||_∞ is pretty small and so an additional TV regularization would in effect make most of the component either -||x||_∞ or +||x||_∞ . Could this implementation marrying a TV and l_infty regularization solver be the equivalent to the low complexity solver of Dror Baron and Marco Duarte ? Could this reach the asymptotics described by Shirin Jalali and Arian Maleki ?

Image Credit: NASA/JPL/Space Science Institute. N00177639.jpg was taken on October 25, 2011 and received on Earth October 26, 2011. The camera was pointing toward TITAN at approximately 1,803,967 kilometers away, and the image was taken using the CL1 and CB3 filters. This image has not been validated or calibrated. A validated/calibrated image will be archived with the NASA Planetary Data System in 2012.

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.