Matrix completion and nuclear norms

Let the sampling operator retain entries indexed by a set $\Omega$ and zero the rest. Noiseless nuclear-norm completion minimizes the sum of singular values subject to matching those observed entries. A rank-$r$ matrix with dimensions $m$ by $k$ has $r(m+k-r)$ local degrees of freedom at a regular rank-$r$ point, but observing that many arbitrary entries is not sufficient. A completely unobserved row or a missed isolated nonzero entry can remain ambiguous despite a small rank.

Incoherence measures how concentrated the singular vector spaces are on coordinate axes. For an orthonormal left singular basis $U$, a common measure is $(m/r)\max_i\|U^\top e_i\|_2^2$, with an analogous right measure. Concentrated directions are easy to miss under entry sampling. Random-sampling recovery theorems therefore impose specified incoherence and rank conditions and a sufficient sample size with logarithmic factors. Their conclusion is probabilistic over an observation model, not a promise that every observation pattern with the same number of entries works.

Write a compact singular value decomposition $M=UDV^\top$ and define the tangent space $T=\{UA^\top+BV^\top\}$ with the natural compatible matrix dimensions. Its orthogonal complement is taken in the Frobenius inner product. Suppose the sampling map is injective on this tangent space. Also suppose there is a matrix supported only on observed entries whose tangent projection is $UV^\top$ and whose orthogonal projection has operator norm strictly below one. Under these two conditions, the target is the unique minimizer of the noiseless convex program.

To see the role of each condition, consider a feasible perturbation whose observed entries vanish. Its inner product with the supported certificate is zero. The nuclear-norm subgradient inequality then forces a strictly positive objective increase whenever its orthogonal tangent component is nonzero, with margin proportional to one minus the certificate’s orthogonal operator norm. If that component is zero, the perturbation lies in the tangent space, and injectivity forces it to vanish. The strict certificate is sufficient; its absence alone is not a converse impossibility theorem.

For a real two-by-two matrix, the squared nuclear norm equals its squared Frobenius norm plus twice the absolute determinant. This follows because the product of its two singular values is the absolute determinant. It makes small completion problems exactly analyzable without numerical optimization. Such examples can show both success and failure of the convex surrogate, even when a missing entry is uniquely determined by a rank-one constraint. A rank constraint and a nuclear penalty are different optimization problems.

Noisy observations require relaxing the equality constraint or using a penalized loss with an appropriate noise level. Exact recovery certificates must then be replaced or supplemented by stability bounds. Missingness that depends on unobserved values also differs from uniform entry sampling. These distinctions matter in applications: a clean theorem for a noiseless incoherent matrix and independent sampling does not justify arbitrary imputation, nor does a visually plausible completion establish uniqueness or uncertainty calibration.