I am trying to understand the concept of matrix completion. I came across the following line ($M$ is a low rank matrix, and we only have few samples of it. The task is to recover the entire matrix from these samples):
To recover a low rank matrix, it cannot be in the null space of the sampling operator. It is easy to see that if the singular vectors of the matrix M are highly concentrated, then M could very well be in the null space of the sampling operator.
I get the first line, things that are mapped to zero by the sampling operator cannot be recovered. It's the second line I don't understand. What does it mean if the singular vectors are highly concentrated?
It means that if you look at the singular values, then you have a few high numbers and a whole bunch of very low numbers.
So, for a 5x5 matrix, singular values of {1,1,0,0,0} could be considered "concentrated" whereas singular values of {1,1, 0.9, 0.8, 0.6} might not be so concentrated.
I think the idea of concentration comes about when you consider the ellipse generated by the singular vectors. If you've decomposed a matrix $A$ so that $A=U\Sigma V^T$, you can ask "what is the image of the unit ball under this ellipse?" If you were to somehow plot this image (which you can do for matrices that are small enough) you would find that the singular vectors are the direction semi-axes of this ellipse, and the singular values spell out how large each axis is. So if you have a singular value of $0$, then the ellipse is flat in that dimension.