  We characterize the first-order sensitivity of approximately recovering a
low-rank matrix from linear measurements, a standard problem in compressed
sensing. A special case covered by our analysis is approximating an incomplete
matrix by a low-rank matrix. We give an algorithm for computing the associated
condition number and demonstrate experimentally how the number of linear
measurements affects it.
  In addition, we study the condition number of the rank-r matrix approximation
problem. It measures in the Frobenius norm by how much an infinitesimal
perturbation to an arbitrary input matrix is amplified in the movement of its
best rank-r approximation. We give an explicit formula for the condition
number, which shows that it does depend on the relative singular value gap
between the rth and (r+1)th singular values of the input matrix.
