Low-Rank Matrix Recovery with Partial Subspace Priors: Degrees of Freedom and Recovery Guarantees

Matrix recovery with prior information, such as subspaces derived from historical data or auxiliary features, has wide applications in recommender systems, signal processing, and multi-label learning. A central challenge is to quantify the information-theoretic measurement savings offered by prior information, and to verify whether these savings are achievable by recovery methods. To address this challenge, we characterize the intrinsic degrees of freedom (DoF) of low-rank matrices under column-subspace priors using quotient-space and Grassmann-manifold geometry. Specifically, we show that for a rank-$r$ matrix $$\begin{gathered} mathbfM \\ in \\ mathbb{R}^{m \\ timesn} \end{gathered}$$ with a known $r_1$-dimensional subspace of its column space, its DoF is equal to $nr+(m-r)(r-r_1)$. This provides a theoretical lower bound on the number of scalar measurements required to guarantee exact recovery. To verify that this lower bound is attainable, we develop a DoF-optimal recovery method (DORM), which relies on a designed two-stage measurement scheme and achieves the exact recovery using a number of measurements equal to the DoF. For general linear measurements, we propose a projected matrix recovery (PMR) framework, which uses subspace priors to reduce the original problem to standard rank-$(r-r_1)$ matrix recovery via measurement-space projection. In particular, under Gaussian measurements, we establish that PMR achieves exact recovery with high probability from $$\begin{gathered} n{r}_1+ \\ mathcalO((r-r_1)(m+n-r)) \end{gathered}$$ measurements, matching the DoF up to a constant factor. Synthetic and real-world experiments demonstrate measurement savings of the proposed methods, consistent with our theoretical analysis.