- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies low-rank matrix recovery with partial subspace priors. For a rank- matrix whose column space contains a known -dimensional subspace, the authors derive the degrees of freedom as . They propose DORM, which achieves this measurement count under a designed sensing operator and a nondegeneracy assumption, and PMR, which projects out the known-subspace contribution and reduces recovery to a lower-rank matrix-sensing problem. Under Gaussian measurements, PMR achieves recovery with a sample complexity matching the degrees of freedom up to constant factors. The paper also provides extensions to simultaneous row and column priors, noise-stability analysis, and experiments on synthetic matrices, recommendation data, and wireless channel data.
Critical strengths
- The paper provides a clear characterization of the degrees of freedom under partial subspace priors and develops two recovery methods with exact or constant-factor measurement guarantees.
- The theoretical analysis is coherent and supported by detailed proofs, including extensions to joint row and column priors and stability bounds under measurement noise.
- The experiments cover synthetic and real-world data, different measurement designs, noisy recovery, and computational scaling, providing broad empirical support for the proposed methods.
Critical weaknesses
- While the main baseline confirms the prior's utility, it fails to isolate the recovery mechanism's specific advantage over similar methods, nor does it fully connect Appendix A's related approaches to the empirical results.
- While these experiments provide valuable practical evidence, they involve unquantified violations of theoretical assumptions: priors are estimated rather than exact (), target matrices are only approximately low-rank, and sampling models diverge from PMR's dense Gaussian ensemble.
- Although Theorem 4.3 and Theorem C.4 rely on theoretical guarantees for Gaussian sensing and stable solvers, the experiments use alternating minimization without verifying those properties or detailing the initialization conditions (Appendix B.8) required to attain the stated sample complexity.
Questions for authors
- Do the Jester and USC experiments target original or truncated low-rank matrices, how closely do historical subspaces satisfy , and which theoretical guarantees apply to their columnwise measurement schemes?
- What initialization, stopping criteria, and convergence assumptions govern PMR’s alternating-minimization solver, and does Theorem 4.3 cover this implementation directly or apply only via an appropriate alternative residual solver?
- What operations, preprocessing, construction, and data transfers are included in Table 3's runtimes (specifically regarding projection timing under simulated effective Gaussian models), and what hardware and memory specs were used?
8 comments
W2. How do inexact priors, approximate low rank, and non-Gaussian sensing affect recovery?
Thank you for highlighting these differences between our theoretical assumptions and practical experiments. DORM primarily provides a constructive demonstration that the DoF bound is attainable. Its exact-DoF guarantee requires a designed measurement scheme, including fully observed anchor columns, and the nondegeneracy condition in Assumption 4.1. These requirements limit its applicability. For practical applications, we favor PMR, which does not require fully observed anchor columns and can use the supplied linear measurement operator. We address the three issues below, distinguishing the applicability of the PMR framework from the conditions needed for its recovery guarantees.
(i) Inexact subspace priors. Following our analysis and experiments in response to Reviewer Cgsa's W2 concerning inexact priors, let be an orthonormal basis for the column space of an exactly rank- target, and let be the supplied orthonormal prior. We quantify their mismatch by
PMR error bound. Let be an orthonormal complement of , and define and for the sensing matrix . Let span with orthonormal columns, and let be the stability constant of the rank- residual solver for . Under noiseless measurements, , full column rank of , and the stated solver stability assumption, we obtain
\leq \sqrt{1+\frac{\\|G_2\\|_2^2}{\sigma_{\min}^2(G_1)}} \left(1+C_{\mathcal H}\\|Q_2^\top G_2\\|_2\right) \varepsilon\\|M\\|_F.$$ Thus, when the amplification factors remain uniformly bounded, PMR's relative recovery error is $O(\varepsilon)$; $\varepsilon=0$ gives exact recovery under these assumptions. **Experiments.** We compare PMR with an exact prior ($\sigma=0$) and a noisy prior $\widetilde U_1=\operatorname{orth}(U_1+\sigma G)$ at $\sigma=10^{-2}$, where $G$ has independent standard Gaussian entries. We use rank-five $30\times50$ matrices with $r_1=3$ and noiseless Gaussian measurements. The table reports the median squared relative error $\\|\widehat M-M\\|_F^2/\\|M\\|_F^2$ over 500 matched trials per measurement budget. | $K$ | PMR exact prior ($\sigma=0$) | PMR , noisy prior ($\sigma=10^{-2}$) | | ---: | ---: | ---: | | 280 | $2.143\times10^{0}$ | $2.163\times10^{0}$ | | 300 | $1.571\times10^{0}$ | $1.665\times10^{0}$ | | 350 | $1.047\times10^{-18}$ | $5.055\times10^{-3}$ | | 400 | $3.141\times10^{-20}$ | $2.759\times10^{-6}$ | | 450 | $1.507\times10^{-21}$ | $4.824\times10^{-15}$ | Prior noise increases the error at smaller budgets, while at $K=450$ the noisy-prior case reaches a median squared relative error below $10^{-14}$. **(ii) Approximately low-rank targets.** The low-rank approximation residual can be treated as effective measurement noise. Let $M_r$ be the best rank-$r$ approximation and write $$M=M_r+E.$$ The original observations then satisfy $$y=\mathcal A(M)=\mathcal A(M_r)+\xi_E, \qquad \xi_E:=\mathcal A(E).$$ Thus, $\mathcal A(E)$ acts as measurement noise when recovering $M_r$, allowing us to use the PMR noise-stability analysis in Theorem C.4 under its sensing and solver assumptions and an exact prior for $M_r$. The reconstruction error relative to the original target then includes both the low-rank approximation error and the recovery error induced by this effective noise.W2 (continued): Measurement models.
(iii) Measurement models. PMR's ability to recover the target matrix depends on whether the effective measurement model in Eq. (28) permits recovery of the residual :
\qquad \mathcal H(X):=Q_2^\top G_2\operatorname{vec}(X).$$ Since $X$ has rank $r-r_1$, if the effective operator $\mathcal H$ satisfies suitable low-rank recovery conditions, a low-rank matrix recovery algorithm can recover $X$. Examples include matrix RIP for nuclear-norm recovery (Recht et al., 2010) and incoherence with sufficient random samples for matrix completion (Recht, 2011). For example, Jester uses random entry sampling and USC uses columnwise Gaussian sensing, both special cases of rank-one measurements. After PMR projection, the effective measurements take the form $$\widetilde y_{j\ell}= �0� _\ell=c_{j\ell}^\top X e_j, \qquad j=1,\ldots,n,\quad \ell=1,\ldots,k_j-r_1,$$ where $k_j$ is the number of observations in column $j$, $e_j$ selects that column, and $c_{j\ell}\in\mathbb R^d$ with $d=m-r_1$. Under the USC measurement scheme, the vectors $c_{j\ell}$ are i.i.d. Gaussian: $c_{j\ell}\overset{\mathrm{iid}}{\sim}\mathcal N(0,I_d/m)$. For Jester, the observed positions are sampled uniformly without replacement, $\Omega_j\sim\operatorname{Unif}\\{\Omega\subseteq\\{1,\ldots,m\\}:|\Omega|=k_j\\}$. For a fixed prior and projection-basis rule, this induces a discrete joint distribution of the weights, with $c_{j\ell}^\top c_{js}=\delta_{\ell s}$, i.e., the weights within each column are orthonormal. Recovery analysis for the effective columnwise rank-one operators $c_{j\ell}e_j^\top$ can draw on the nuclear-norm minimization proof framework in Recht (2011), and the alternating-minimization recovery analyses of Jain et al. (2013) for matrix completion and Nayer and Vaswani (2021) for the linear columnwise-sensing specialization. Our Jester and USC experiments use application-specific sampling schemes and demonstrate PMR's applicability beyond dense Gaussian sensing. In the revised paper, we will discuss recovery under non-Gaussian and other structured measurement models, including the required incoherence and sampling conditions. **References** - Recht, B., Fazel, M., and Parrilo, P. A. (2010). Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. SIAM Review, 52(3):471–501. - Recht, B. (2011). A Simpler Approach to Matrix Completion. Journal of Machine Learning Research, 12:3413–3430. - Jain, P., Netrapalli, P., and Sanghavi, S. (2013). Low-rank Matrix Completion Using Alternating Minimization. Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pp. 665–674. - Nayer, S., and Vaswani, N. (2021). Sample-Efficient Low Rank Phase Retrieval. IEEE Transactions on Information Theory, 67(12):8190–8206. **W3. How do the experimental sensing model and alternating-minimization initialization satisfy the assumptions of Theorems 4.3 and C.4?** In the PMR experiment in Figure 1(b), the sensing matrices $A_k$ have i.i.d. Gaussian entries, consistent with our theoretical setting. It is worth noting that Step 2 of Algorithm 2 recovers the rank-$(r-r_1)$ matrix $X$ from the projected measurements in Eq. (28), reducing the task to a standard low-rank matrix-sensing problem. As discussed in Appendix B.8, methods such as nuclear-norm minimization, alternating minimization, and singular value projection achieve recovery using $\mathcal O((r-r_1)(m+n-r))$ effective Gaussian measurements. In our experiments, we use alternating minimization with spectral initialization. Under the RIP and initialization conditions in Jain et al. (2013), alternating minimization converges to the true matrix. Therefore, alternating minimization requires $\mathcal O((r-r_1)(m+n-r))$ Gaussian measurements to recover the rank-$(r-r_1)$ matrix $X$ under these conditions. We will clarify the recovery algorithm and its required conditions in Theorem 4.3. For initialization, we factorize $X=VR$, where $V\in\mathbb R^{(m-r_1)\times q}$, $R\in\mathbb R^{q\times n}$, and $q=r-r_1$. We first form $S_0=\mathcal H^*(\widetilde y)\in\mathbb R^{(m-r_1)\times n}$, where $\mathcal H^*$ is the adjoint of the projected sensing operator. This back-projected matrix provides a spectral estimate of the column space of $X$. Taking its SVD, $S_0=U\Sigma W^\top$, we initialize the two factors as $$V^{(0)}=U_{[:,1:q]},\qquad R^{(0)}\in\arg\min_{R\in\mathbb R^{q\times n}} \\|\mathcal H(V^{(0)}R)-\widetilde y\\|_2^2.$$ Thus, the initial estimate is $X^{(0)}=V^{(0)}R^{(0)}$, and the two factors are subsequently updated by alternating minimization. The common normalization of the operator and observations in the code leaves both initialization steps unchanged.
We thank the reviewer for the thoughtful feedback and constructive suggestions, and address all the weaknesses and questions raised below.
W1. How do the methods compare with prior-aware baselines in Appendix A?
Thank you for highlighting this point. We now include comparisons with three prior-aware baselines discussed in Appendix A: OCMC (Chang et al., 2025), DirtyIMC (Chiang et al., 2015), and subspace-weighted nuclear norm minimization (WeightedNN) (Eftekhari et al., 2018). The three baselines use convex nuclear-norm optimization with weights balancing prior-explained and remaining components, as illustrated by Eqs. (40) and (42) in Appendix A. Both DORM and PMR avoid the need for an additional regularization weight to balance the known and unknown subspaces. This reduces the tuning effort and sensitivity associated with weight selection, making the methods easier to use in practice.
We compare both measurement protocols using 30×50 matrices with r=5, r1=3, and d=300, over 100 trials per sampling point. For a fair comparison, all applicable methods share the same observations and prior within each trial. Baseline weights are selected on independent validation data before testing. The tables report success rates (%), with success defined by ∣M−M∣F2/∣M∣F2<10−6.
Table 1. DORM-designed measurements (r=5, r1=3). The first two columns are fully observed, and Gaussian linear measurements are applied to the remaining columns. The 60 scalar observations in the two anchor columns are included in K. All five methods share this same measurement operator.
Under DORM-designed measurements, DORM achieves 100% success at K=d, illustrating attainability of the DoF bound under its stated assumptions. PMR achieves 98% success at K=1.3d, while OCMC and DirtyIMC first reach at least 95% on the tested grid at K=1.75d, and WeightedNN at K=2d. Thus, PMR also requires fewer measurements than the three convex baselines to reach this success level in this experiment.
Table 2. Full Gaussian measurements (r=5, r1=3). We use the original PMR sensing ensemble: yk=⟨Ak,M⟩F, with $
Ak_{ij}\stackrel{\mathrm{iid}}{\sim}\mathcal N(0,1/K)$ over the entire matrix. PMR and the three baselines share identical sensing operators and observations. DORM is N/A because this protocol does not provide the fully observed anchor columns required by its recovery procedure.
Under full Gaussian measurements, PMR achieves 99% success at K=1.2d, while the three convex baselines first reach at least 95% on the tested grid at K=1.75d. This demonstrates PMR's measurement efficiency under Gaussian sensing for the stated experimental setting.
References