I am seeking a clarification of the concept of Incoherence within the MC framework.


1) the literature mentions the application of a "strong incoherence" given a set of assumptions. Intuitively, how is the strong incoherence different than "incoherence".

2) Does the Restricted Isometry Property have anything to do with low rank Matrix Completion of natural images, or does it only pertain to the reconstruction of signals in CS (i.e. y = Ax).


There is an incoherence property $\mu$ used in CS to measure the correlation between the sensing and representation bases; whereby low correlation enables signal reconstruction of sparse signals with fewer samples and high correlation makes it nearly impossible regardless of the sparsity of the signal.

For MC, there is also an incoherence property $\mu$: it measures the correlation between the singular vectors of the matrix (U and V from SVD) and the standard basis vectors (i.e. $\ e_i$ = vector of zeros except for a 1 at index i). As with CS, low rank (i.e. singular value-sparse) matrices exhibiting a low correlation are more likely to be reconstructed than those with high correlation.

Both of these incoherence properties are used to stipulate the minimum number of samples required to reconstruct a signal (1D, 2D, respectively). However, I cannot see where the matrix incoherence property addresses the nature of the sampling; I.e. it only tells me which matrices are more likely to be reconstructed. I believe this is because the "nature of the sampling" that is assumed (by CS community doing MC) for low rank MC problems is strictly "uniform random sampling".

Now, restricting our attention only to those low rank matrices with low $\mu$, is there an additional MC incoherence property that characterizes the nature of the sampling to say whether or not a matrix can be reconstructed? (I'm looking for a link back to CS where they compare the relationships between different representation/sensing bases to see if they work well together to reconstruct the signal.)

Thank you.


1 Answer 1


Partial answer:

2) Matrix completion does "not rely on any notions of restricted isometry." Candes and Recht, 2008.

  • $\begingroup$ can you add more information? $\endgroup$
    – MimSaad
    Apr 12, 2017 at 21:42
  • $\begingroup$ @MimSaad: I would delete the answer if I could. $\endgroup$
    – val
    Apr 12, 2017 at 21:46
  • $\begingroup$ I guess you can't delete the question, but you can delete the answer, anyway if you have some useful information, please add and I'll upvote it. $\endgroup$
    – MimSaad
    Apr 12, 2017 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.