Echoing, Yonina Eldar's comment that the nuclear norm was not a very good proxy for the rank functional in the imaging business, here is another data point by Xiaoxiao Shi and Philip Yu in the matrix completion business. Maybe they should take a look at the log-det heuristics instead or avoid the proxy issue altogether? I like these negative results papers, however, one should not read too much into them, there are helpful warning signs for the busy person, but either the domain in which this algorithm is applied is not optimal or better techniques are known by others in the field. I wish it were said more forcefully though. Here is the paper: Limitations of Matrix Completion via Trace Norm Minimization by Xiaoxiao Shi and Philip S. Yu. The abstract reads:
In recent years, compressive sensing attracts intensive attentions in the field of statistics, automatic control, data mining and machine learning. It assumes the sparsity of the dataset and proposes that the whole dataset can be reconstructed by just observing a small set of samples. One of the important approaches of compressive sensing is trace norm minimization, which can minimize the rank of the data matrix under some conditions. For example, in collaborative filtering, we are given a small set of observed item ratings of some users and we want to predict the missing values in the rating matrix. It is assumed that the users' ratings are affected by only a few factors and the resulting rating matrix should be of low rank. In this paper, we analyze the issues related to trace norm minimization and find an unexpected result that trace norm minimization often does not work as well as expected.
'
Image Credit: NASA/JPL-Caltech/Cornell/ASU. Ridout' Rock on Rim of Odyssey Crater
NASA's Mars Exploration Rover Opportunity looked across a small crater on the rim of a much larger crater to capture this raw image from its panoramic camera during the rover's 2,685th Martian day, or sol, of work on Mars (Aug. 13, 2011).
Images and Captions
Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from
3 comments:
Sanity check:
Eq (6) is not, unlike what's described in the text, eq (5) with entries dropped. As a result, eq (6) is doubly wrong. Is that right?
They take eq 5 as an example.
Then drop some number shown with ? in eq 6.
They then use SVT to recover 5 from 6 but they get 7 instead.
They are just showing that in some cases, the solution is not unique and you can therefore get different solutions from different solvers. While it is a valid point, it also neglect the context in which this solver was used (maybe the solver is not good for the assumption that these matrices fulfill).
Did I answer your question ?
Cheers,
Igor.
Post a Comment