Can Netflix give you Superman's X-ray vision ?

In If there is revolution in rank minimization and nobody hears about it, is this a revolution ?, I listed a set of the different proxies for the rank functional. Vicente Malave kindly mentioned the following:

Another norm with some good theoretical and empirical improvement (matrix completion / netflix type problems) over the nuclear norm is the max norm, which has gotten attention mostly through the work of Nati Srebro .

Thanks Vicente, I nearly forgot about that one, most probably because I have not seen any implementation of it anywhere. The following paper [1] provides some good background as to why the max-norm is potentially interesting. 


But in the end, why should we care about this flurry of proxies? sure everybody gets famous writing the latest and greatest paper on how they improved their Netflix RSME...a little too late. I mean really, what's the point of all this ? Doing better Boogie-Boogie Jam-Jam collaborative filtering systems, maybe ? Call me a dreamer, but these other proxies are important because they might provide us with better bounds on the lower number of measurements needed to reconstruct signals when phase information is lost. Right now, the PhaseLift [2] approach tells us that the number of measurements is 3n for 1D signals in the noiseless case. This approach makes absolutely no argument on the sparsity of the signal is used. What if it did ? The authors finish their paper with:

.....At the theoretical level, we need to understand for which families of physically implementable structured illuminations does the trace-norm heuristic succeed?[My emphasis] How many diffraction patterns are provably sufficient for our convex programming approach to work? Also, we have shown that our approach is robust to noise in the sense that the performance degrades very gracefully as the SNR decreases. Can this be made rigorous? Can we prove that our proposed framework is indeed robust to noise? Here, it is very likely that the tools and ideas developed in the theories of compressed sensing and of matrix completion will play a key role in addressing these fundamental issues....

In effect, the proxies may have some importance on the type of probing illumination used and their instantiation through actual hardware development. Forget your Netflix RMSE score, this is important.

References:
[1] Concentration-Based Guarantees for Low-Rank Matrix Reconstruction by Rina Foygel, Nathan Srebro. The abstract reads:

We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-norm, and present reconstruction guarantees based on existing analysis on the Rademacher complexity of the unit balls of these norms. We show how these are superior in several ways to recently published guarantees based on specialized analysis.

[2] PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
Emmanuel J. Candes, Thomas Strohmer and Vladislav Voroninski.

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.