Lower bounds for the low-rank matrix approximation

Low-rank matrix recovery is an active topic drawing the attention of many researchers. It addresses the problem of approximating the observed data matrix by an unknown low-rank matrix. Suppose that A is a low-rank matrix approximation of D, where D and A are [Formula: see text] matrices. Based on a useful decomposition of [Formula: see text], for the unitarily invariant norm [Formula: see text], when [Formula: see text] and [Formula: see text], two sharp lower bounds of [Formula: see text] are derived respectively. The presented simulations and applications demonstrate our results when the approximation matrix A is low-rank and the perturbation matrix is sparse.