Wednesday, October 12, 2011

If there is revolution in rank minimization and nobody hears about it, is this a revolution ?

In Heuristics for Rank Proxy and how it changes everything...., I mentioned how some folks found out that log-det was a better heuristics than the nuclear norm for a proxy to the rank functional when searching for low rank solutions. In Information Theoretical Clustering via Semidefinite ProgrammingMeihong Wang and Fei Sha are arguing against the log-det heuristic. In the same vein, in Limitations of Matrix Completion via Trace Norm Minimization,  Xiaoxiao Shi and Philip S. Yu argue about the shortfall of the trace norm approach ( All is not well with the Nuclear norm world...). All these attempts that are quantifying the usefulness of some proxy are useful until you realize that there is a flurry of approaches to rank minimization either using other proxies for the rank functional or different approximations to the low rank problematic, here are the few I have noticed so far (comments are welcome):

One of the reason of the success of  the Donoho-Tanner phase transition stems not only because it shows some uniformity of results across different measurement matrices, but also because of its ability to directly compare different solvers/approaches to sparse recovery. As an example, the latest result on sparse recovery became obviously important when it could directly be compared to the then "gold standard" of the Donoho-Tanner phase transition (see also the results of Bob Sturm)

Similar phase transitions have been observed for these low rank matrix recovery problems. Shouldn't there be some sort of standard against which most algorithm implementations ought to compare their results to so that we collectively devise a better mental picture of what is really working ? Because right now to be honest, I can't. Why is this important ? The message passing algorithms that have pretty made a dent against the L_1 recovery used in compressive sensing, are now, unsurprisingly, applied to rank minimization [1]. If there is revolution in rank minimization and nobody hears about it, is this a revolution ?

Credit: NASA, Navigation Camera Sol 2738


Vicente Malave said...

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 .

Igor said...

Thanks Vicente,

I nearly forgot about that one