Deterministic certificates for structured low-rank matrices.

Source abstract

We study deterministic certificates for matrix optimization under a prescribed real-linear structure. A rank-stable projection condition gives a computable structured low-rank approximation whenever the projected truncation preserves the target rank. For nuclear-norm regularization, a projected optimality certificate and restricted injectivity imply uniqueness. For rank-penalized least squares, rank-stratified exclusion tests are derived under restricted curvature, and a Hermitian example verifies the criterion. The results identify spectral, structural, and measurement conditions that can be checked without a random sampling model.