# Incoherence: Compressed Sensing (CS) vs Matrix Completion (MC)

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

Specifically,

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).

Background

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.