acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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- matrix with a known -dimensional subspace of its column space, its DoF is equal to . 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- matrix recovery via measurement-space projection. In particular, under Gaussian measurements, we establish that PMR achieves exact recovery with high probability from 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.

Primary area:
optimization
Keywords:
Low-rank matrix recovery, Partial subspace priors, Degrees of freedom, Measurement complexity, Gaussian sensing

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NVpLOpenReview ↗
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-rr matrix M∈Rm×nM\in\mathbb{R}^{m\times n} whose column space contains a known r1r_1-dimensional subspace, the authors derive the degrees of freedom as nr+(m−r)(r−r1)nr+(m-r)(r-r_1). 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
  1. 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.
  2. The theoretical analysis is coherent and supported by detailed proofs, including extensions to joint row and column priors and stability bounds under measurement noise.
  3. 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
  1. 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.
  2. While these experiments provide valuable practical evidence, they involve unquantified violations of theoretical assumptions: priors are estimated rather than exact (U1⊆col⁡(M)U_1 \subseteq \operatorname{col}(M)), target matrices are only approximately low-rank, and sampling models diverge from PMR's dense Gaussian ensemble.
  3. 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
  1. Do the Jester and USC experiments target original or truncated low-rank matrices, how closely do historical subspaces satisfy U1⊆col⁡(M)U_1 \subseteq \operatorname{col}(M), and which theoretical guarantees apply to their columnwise measurement schemes?
  2. 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?
  3. 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

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×5030\times50 matrices with r=5r=5, r1=3r_1=3, and d=300d=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\\|\widehat M-M\\|_F^2/\\|M\\|_F^2 < 10^{-6}.

Table 1. DORM-designed measurements (r=5r=5, r1=3r_1=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 KK. All five methods share this same measurement operator.

KKK/dK/dDORMPMROCMCDirtyIMCWeightedNN
2700.9000000
3001.001000000
3301.1010029000
3601.2010089000
3901.3010098000
4501.50100100330
5251.751001009610090
6002.00100100100100100
7502.50100100100100100
9003.00100100100100100

Under DORM-designed measurements, DORM achieves 100% success at K=dK=d, illustrating attainability of the DoF bound under its stated assumptions. PMR achieves 98% success at K=1.3dK=1.3d, while OCMC and DirtyIMC first reach at least 95% on the tested grid at K=1.75dK=1.75d, and WeightedNN at K=2dK=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=5r=5, r1=3r_1=3). We use the original PMR sensing ensemble: yk=⟨Ak,M⟩Fy_k=\langle A_k,M\rangle_F, with $

AkA_k

_{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.

KKK/dK/dDORMPMROCMCDirtyIMCWeightedNN
2700.90N/A0000
3001.00N/A0000
3301.10N/A88000
3601.20N/A99000
3901.30N/A100000
4501.50N/A10044446
5251.75N/A100100100100
6002.00N/A100100100100
7502.50N/A100100100100
9003.00N/A100100100100

Under full Gaussian measurements, PMR achieves 99% success at K=1.2dK=1.2d, while the three convex baselines first reach at least 95% on the tested grid at K=1.75dK=1.75d. This demonstrates PMR's measurement efficiency under Gaussian sensing for the stated experimental setting.

References

  • Chang, G., Zhang, W., and Zhang, L. (2025). Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection. Proceedings of the 42nd International Conference on Machine Learning, 267:7393–7416.
  • Chiang, K.-Y., Hsieh, C.-J., and Dhillon, I. S. (2015). Matrix Completion with Noisy Side Information. Advances in Neural Information Processing Systems, 28.
  • Eftekhari, A., Yang, D., and Wakin, M. B. (2018). Weighted Matrix Completion and Recovery with Prior Subspace Information. IEEE Transactions on Information Theory, 64(6):4044–4071.

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 UU be an orthonormal basis for the column space of an exactly rank-rr target, and let U~1\widetilde U_1 be the supplied orthonormal prior. We quantify their mismatch by

ε=∣(I−UU⊤)U~1∣2=sin⁡θmax⁡.\varepsilon=\\|(I-UU^\top)\widetilde U_1\\|_2=\sin\theta_{\max}.

PMR error bound. Let U~⊥\widetilde U_\perp be an orthonormal complement of U~1\widetilde U_1, and define G1=A(In⊗U~1)G_1=A(I_n\otimes\widetilde U_1) and G2=A(In⊗U~⊥)G_2=A(I_n\otimes\widetilde U_\perp) for the sensing matrix AA. Let Q2Q_2 span col⁡(G1)⊥\operatorname{col}(G_1)^\perp with orthonormal columns, and let CHC_{\mathcal H} be the stability constant of the rank-(r−r1)(r-r_1) residual solver for H(Z)=Q2⊤G2vec⁡(Z)\mathcal H(Z)=Q_2^\top G_2\operatorname{vec}(Z). Under noiseless measurements, K>nr1K > nr_1, full column rank of G1G_1, 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 MM depends on whether the effective measurement model in Eq. (28) permits recovery of the residual X=U⊥⊤MX=U_\perp^\top M:

\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.
Reviewer_eECQOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies low-rank matrix recovery with partial column subspace priors. It derives the remaining degree of freedom (DoF) and proposes DORM, which achievs this DoF through designed measurements, and PMR, which reduces Gaussian sensing to standard low-rank recovery. Experiments confirms measurement savings.

Critical strengths

The two algorithms can utilize the column subspace prior to reduce the number of measurements. DORM attains the degree of freedom under its designed measurements and nondegeneracy condition, and PMR eliminates the unknown known-subspace coefficients through measurement-space projection and leaves a standard rank (r-r1) recovery problem.

Critical weaknesses
  1. Limited technical novelty. The DoF formula follows diretly from decomposing the matrix into nr1nr_1 unrestricted coefficients and a standard rank-(r−r1)(r-r_1) residual. PMR then uses projection in measurement space and Gaussian rotational invariance to invoke existing low-rank matrix recovery guarantees. DORM similarly combines selected-column subspace estimation with least-squares recovery. Although these constructions are useful, the paper does not sufficiently establish a substantial technical advance beyond this combination of established ideas. This weakens the orginality of its theoretical and algorithmic contributions.

  2. Insufficient evidence of scalability to practical matrix dimensions. The matrix tested is at most 1000×10001000\times 1000 and it does not establish performance at much larger row or column encountered in real-world applications. Moreover, the largest PMR benchmark directly simulates the effective Gaussian model, and it is unclear the cost of transforming a supplied original sensing operator. Peak memory usage is also not reported. Given the projection and dense least-squares operations, the reported results therefore leave unclear whether the methods can handle application-scale matrices within practical runtime and momory budgets.

Questions for authors
  1. Could the authors clarify the main technical advances beyond standard dimension counting, measurement-space projection, and existing low-rank recovery results? Which new proof ideas are essential to establishing the proposed guarantees?

  2. Could the authors clarify how runtime and memory requirements scale to practical matrix dimensions, such as 105−−10610^5--10^6 users or items in recommendation systems? What evidence supports scalability beyond the 1000×10001000\times 1000 matrices tested in the appendix?

4 comments

We thank the reviewer for the thoughtful feedback and constructive suggestions, and address all the weaknesses and questions raised below.

W1. What is new beyond standard dimension counting and projection?

There are several ways to derive the DoF of the low-rank matrix under partial subspace information. In the paper, we count the (m−r)(r−r1)(m-r)(r-r_1) degrees of freedom needed to specify the column space given the prior, then add the nrnr coefficients in a basis of that space. Alternatively, we can derive the same DoF count inspired by the procedures of PMR. Specifically, the total DoF is the sum of the degrees of freedom of R1R_1 and XX in Eq. (16). The coefficient matrix R1∈Rr1×nR_1\in\mathbb{R}^{r_1\times n} contributes nr1nr_1 degrees of freedom, and the residual matrix X∈R(m−r1)×nX\in\mathbb{R}^{(m-r_1)\times n} has rank r−r1r-r_1 and contributes (r−r1)(m+n−r)(r-r_1)(m+n-r) degrees of freedom. Our contribution is to quantify how much a partial column-space prior saves and to establish when that saving translates into fewer measurements.

  • DoF reduction. Knowing an r1r_1-dimensional subspace of the column space reduces the matrix DoF by r1(m−r)r_1(m-r), yielding a measurement lower bound of d=nr+(r−r1)(m−r)d=nr+(r-r_1)(m-r). This bound provides a theoretical reference for the number of measurements needed for recovery when partial subspace information is available.

  • Attainability with DORM with two-stage measurement design. DORM provides a constructive proof that the DoF lower bound is attainable. Under our two-stage measurement design, DORM recovers the target matrix almost surely from exactly dd noiseless measurements under Assumption 4.1. This attainability result supports our approach to deriving the matrix DoF from the dimension of Grasmannion subspace.

  • Recovery through projection without prior-weight tuning. Our methods exploit subspace priors through projection; in particular, PMR transforms the original problem into a lower-rank matrix recovery problem in the projected measurement space. Unlike OCMC (Chang et al., 2025), DirtyIMC (Chiang et al., 2015), and WeightedNN (Eftekhari et al., 2018), which use regularization weights to balance prior-explained and remaining components (Appendix A, Eqs. (40) and (42)), neither DORM nor PMR requires such a weight. This avoids the associated tuning cost and sensitivity. Using full Gaussian measurements under the simulation settings in the paper, the following comparison shows that PMR requires fewer measurements than these prior-aware baselines to achieve high recovery success rates.

    KKK/dK/dPMROCMCDirtyIMCWeightedNN
    2700.900000
    3001.000000
    3301.1088000
    3601.2099000
    3901.30100000
    4501.5010044446
    5251.75100100100100
    6002.00100100100100
    7502.50100100100100
    9003.00100100100100
  • Measurement noise and inexact priors. We analyze stability under additive measurement noise and test sensitivity to perturbations of the prior subspace. Please see our responses to Reviewer Cgsa's W2 / Q1 and Reviewer NVpL's W2 and Q1 for the analysis and experiments concerning inexact priors and their effects on recovery.

References

  • Chang, G., Zhang, W., and Zhang, L. (2025). Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection. Proceedings of the 42nd International Conference on Machine Learning, 267:7393–7416.
  • Chiang, K.-Y., Hsieh, C.-J., and Dhillon, I. S. (2015). Matrix Completion with Noisy Side Information. Advances in Neural Information Processing Systems, 28.
  • Eftekhari, A., Yang, D., and Wakin, M. B. (2018). Weighted Matrix Completion and Recovery with Prior Subspace Information. IEEE Transactions on Information Theory, 64(6):4044–4071.

W2. Please report large-scale runtime, operator-transformation cost, and peak memory.

Thank you for pointing out the missing scalability evidence. We have added a computational and storage analysis and new benchmarks starting from the original measurements, including matrices of size 100000×1000100000\times1000 and, for uniform entry sampling, 1000000×10001000000\times1000.

Computational and storage complexity. Let d=nr+(r−r1)(m−r)d=nr+(r-r_1)(m-r) and assume K=O(d)K=O(d). For fixed ranks r,r1r,r_1 and a fixed measurement batch size, the following bounds include operator transformation, initialization, recovery, and assembly of the full output matrix. Here TT is the number of outer ALS iterations and LL is the average number of conjugate-gradient (CG) iterations per left-factor update. The bounds describe the implementations evaluated below.

We consider three settings with a partial subspace prior: DORM with two-stage designed measurements and direct least-squares recovery; PMR with Gaussian measurements and direct ALS updates; and PMR with uniform entry sampling and CG-based left-factor updates.

Algorithm and measurement schemeTotal computational complexityPeak storage complexity
Partial-prior DORM: designed measurementsO(mn2+n3)O(mn^2+n^3)O(mn+n2)O(mn+n^2)
Partial-prior PMR: Gaussian measurements, direct ALSO((T+1)(m+n)(m2+n2))O((T+1)(m+n)(m^2+n^2))O(m2+mn+n2)O(m^2+mn+n^2)
Partial-prior PMR: uniform entry sampling, CG left-factor updatesO(mnmin⁡(m,n)+T(L+1)(m+n))O(mn\min(m,n)+T(L+1)(m+n))O(mn)O(mn)

For DORM, the main costs are constructing the reduced sensing matrix and solving the coefficient least-squares problem. For Gaussian PMR, the dense factor-update least-squares systems dominate computation and storage. For entry sampling, CG applies the left-factor operator without storing its full coefficient matrix; dense spectral initialization contributes O(mnmin⁡(m,n))O(mn\min(m,n)) time, while initialization and full output assembly require O(mn)O(mn) storage.

Runtime and peak GPU memory. We ran five seeds per configuration on an RTX 4090 (24 GiB), using FP32, r=5r=5, r1=2r_1=2, noiseless observations, and an exact prior. Recovery time includes transformation of the original sensing operator, projection, initialization, iterative recovery, coefficient refitting, and full output assembly, as applicable.The tables report mean recovery time ±\pm sample standard deviation and the maximum peak GPU tensor allocation across five runs, measured from input preparation through reconstruction.

(i) DORM with designed measurements, K=dK=d.

Matrix sizeKKRecovery time (s)Peak GPU memory (MiB)
100×100100\times1007850.031±0.0080.031\pm0.00813.9
400×400400\times4003,1850.0290±0.00050.0290\pm0.0005101.2
1000×10001000\times10007,9850.135±0.0010.135\pm0.001592.2
100000×1000100000\times1000304,98511.855±0.03411.855\pm0.0346860.3

(ii) PMR with Gaussian measurements, K=⌈1.5d⌉K=\lceil1.5d\rceil.

Matrix sizeKKRecovery time (s)Peak GPU memory (MiB)
100×100100\times1001,1780.358±0.0130.358\pm0.01316.8
400×400400\times4004,7782.491±0.0312.491\pm0.031154.6
1000×10001000\times100011,97862.621±0.08862.621\pm0.088790.4
100000×1000100000\times1000457,478Not run: exceeds capacity—

Under Gaussian sensing, the direct-ALS implementation stores large dense matrices for factor updates, exceeding GPU memory at this scale. Uniform entry sampling avoids storing these matrices and substantially reduces memory usage.

(iii) PMR with uniform entry sampling, K≈3dK\approx3d (rounded per column).

Matrix sizeKKRecovery time (s)Peak GPU memory (MiB)
100×100100\times1002,4000.177±0.0350.177\pm0.0359.0
400×400400\times4009,6000.220±0.0180.220\pm0.01810.9
1000×10001000\times100024,0000.309±0.0710.309\pm0.07132.6
100000×1000100000\times1000915,0002.880±0.1662.880\pm0.1661567.6
1000000×10001000000\times10009,015,0009.863±1.8869.863\pm1.88615509.0

These results extend the runtime and memory evaluation to million-row matrices, showing that PMR with uniform entry sampling can run at this scale within the available GPU memory and practical runtime budgets.

Q1. What are the key technical advances and new proof ideas?

As discussed in our response to W1, our main contributions are:

  • DoF characterization and attainability. We quantify the remaining DoF under a known partial column-space prior as d=nr+(r−r1)(m−r)d=nr+(r-r_1)(m-r) and constructively establish its attainability through DORM. Its two-stage measurement design recovers the missing column subspace and then the remaining coefficients, achieving exact recovery from dd noiseless measurements almost surely under Assumption 4.1.
  • Practical recovery through PMR. PMR accommodates fixed sampling schemes and achieves a measurement requirement proportional to the DoF under Gaussian sensing. Its proof uses the preservation of Gaussian structure after eliminating the known-space coefficients to apply existing low-rank recovery guarantees. Compared with DirtyIMC, OCMC, and WeightedNN, PMR requires no additional regularization weight to balance the known and unknown subspaces (see Appendix A, Eqs. (39) and (42)), simplifying practical use. Our added Gaussian-sensing experiments show that PMR achieves 99% success at K=1.2dK=1.2d, while the three baselines first reach at least 95% at K=1.75dK=1.75d on the tested grid.

Q2. Can the methods scale to 10510^5--10610^6 users or items?

As detailed in our response to Weakness 2 (W2), we evaluated PMR with uniform entry sampling on matrices with up to 10610^6 rows. For fixed ranks r,r1r,r_1, a fixed batch size, and K=O(d)K=O(d), its computational and storage requirements are:

Algorithm and measurement schemeTotal computational complexityPeak storage complexity
PMR: uniform entry samplingO(mnmin⁡(m,n)+T(L+1)(m+n))O(mn\min(m,n)+T(L+1)(m+n))O(mn)O(mn)

Here TT and LL denote the outer ALS iterations and average CG iterations per left-factor update; for fixed n,T,Ln,T,L and m≥nm\ge n, both time and storage scale linearly with mm.

The table below summarizes recovery time and peak GPU memory for uniform entry sampling, using the same settings as in W2.

Matrix sizeKKRecovery time (s)Peak GPU memory (MiB)
100×100100\times1002,4000.177±0.0350.177\pm0.0359.0
400×400400\times4009,6000.220±0.0180.220\pm0.01810.9
1000×10001000\times100024,0000.309±0.0710.309\pm0.07132.6
100000×1000100000\times1000915,0002.880±0.1662.880\pm0.1661567.6
1000000×10001000000\times10009,015,0009.863±1.8869.863\pm1.88615509.0

At 1000000×10001000000\times1000, PMR runs in an average of 9.863 seconds with a peak GPU allocation of approximately 15.15 GiB. This provides runtime and memory evidence at the requested million-row scale under uniform entry sampling.

We hope that our responses have addressed the reviewer's concerns.

Thank you for the clarification. I am now convinced the scalability of the algorithms. However, my concerns regarding on the limited technical contributions remain. Therefore, I will raise my score, though I still lean negative.

Reviewer_CgsaOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper studies low-rank matrix recovery when part of the column space is known in advance (for example, from historical data). The main question is information-theoretic: what is the minimum number of linear measurements required, independent of the recovery algorithm? Additionally, are there algorithms that reach this minimum?

For the first task, the authors prove the minimum number of linear measurements needed to reconstruct the matrix MM, using Grassmann-manifold geometry. For a rank-rr matrix M∈Rm×nM \in \mathbb{R}^{m \times n} with a known r1r_1-dimensional subspace of its column space, the degrees of freedom (DoF) are nr+(m−r)(r−r1)nr + (m-r)(r-r_1). The first term, nrnr, counts the coefficients of MM once its column space is fixed and completely known, and the second term, (m−r)(r−r1)(m-r)(r-r_1), counts what remains unknown about the column space. The formula recovers the classical (m+n−r)r(m+n-r)r when there is no prior (r1=0r_1 = 0), and nrnr when the full column space is known (r1=rr_1 = r).

Two methods are addressed in the second part:

  1. DORM: It recovers the matrix in two steps. First, it observes the first r−r1r-r_1 columns and uses them, together with the known subspace, to identify the complete column space. Second, it recovers the remaining columns using Gaussian measurements and least squares. An important point is their assumption (Assumption 4.1): the first r−r1r-r_1 columns must contain enough independent information to identify all the missing subspace directions.
  2. PMR: It uses random measurements and the known subspace to simplify the recovery problem. It removes the contribution of the known subspace, then recovers a smaller rank-(r−r1)(r-r_1) matrix. Finally, it reconstructs the original matrix.
Critical strengths
  1. Clean and correct formula: The paper provides a simple and intuitive DoF formula, nr+(m−r)(r−r1)nr + (m-r)(r-r_1), for low-rank matrices with partial and full column-subspace information.
  2. DoF-optimal recovery: The proposed DORM method achieves exact recovery using a number of measurements equal to the theoretical DoF under its stated assumptions.
  3. Extension to Gaussian measurements: PMR extends the approach to general Gaussian measurements without requiring DORM's specialized measurement design.
Critical weaknesses
  1. Lack of prior-aware baselines: The experiments only compare the proposed methods with the AM method, which does not use the prior information. Therefore, they demonstrate the benefit of using prior information but do not establish whether DORM or PMR outperform existing prior-aware recovery methods. A fair evaluation should include prior-aware baselines under the same measurement conditions.
  2. Exact subspace assumption: The theoretical results and synthetic experiments assume that the known subspace U1U_1 lies exactly within the true column space of MM, i.e., col(U1)⊆col(M)\mathrm{col}(U_1) \subseteq \mathrm{col}(M). However, in practice, subspace priors are estimated from historical data and may be inaccurate. The real-world experiments use such estimated priors, but their accuracy and impact on recovery are not evaluated. An inaccurate prior may invalidate the assumed reduced-rank structure (rank-(r−r1)(r-r_1) after removing the known subspace) and introduce reconstruction errors. The paper should evaluate robustness to imperfect priors, for example by varying the principal angles between the known and true subspaces and evaluating the resulting recovery performance.
Questions for authors
  1. How do DORM and PMR behave when the prior is inexact, i.e., when col(U1)⊈col(M)\mathrm{col}(U_1) \not\subseteq \mathrm{col}(M)? Is there any error bound for this case?
  2. How realistic is DORM's full-column observation outside offline data? For example, in a live recommender system, full-column observations may not be available.
  3. Why did you not compare your results with subspace-prior baselines?
8 comments

We thank the reviewer for the thoughtful feedback and constructive suggestions, and address all the weaknesses and questions raised below.

W1. Please compare with prior-aware baselines under matched measurements.

Thank you for this suggestion. We have added comparisons with three prior-aware baselines: 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. However, neither of our proposed methods, DORM and PMR, requires an additional regularization weight to balance the known and unknown subspaces. This avoids the additional tuning cost and sensitivity associated with choosing such weights, simplifying practical use.

We compare both measurement protocols using 30×5030\times50 matrices with r=5r=5, r1=3r_1=3, and d=300d=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\\|\widehat M-M\\|_F^2/\\|M\\|_F^2 < 10^{-6}.

Table 1. DORM-designed measurements (r=5r=5, r1=3r_1=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 KK. All five methods share this same measurement operator.

KKK/dK/dDORMPMROCMCDirtyIMCWeightedNN
2700.9000000
3001.001000000
3301.1010029000
3601.2010089000
3901.3010098000
4501.50100100330
5251.751001009610090
6002.00100100100100100
7502.50100100100100100
9003.00100100100100100

Under DORM-designed measurements, DORM achieves 100% success at K=dK=d, illustrating attainability of the DoF bound under its stated assumptions. PMR achieves 98% success at K=1.3dK=1.3d, while OCMC and DirtyIMC first reach at least 95% on the tested grid at K=1.75dK=1.75d, and WeightedNN at K=2dK=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=5r=5, r1=3r_1=3). We use the original PMR sensing ensemble: yk=⟨Ak,M⟩Fy_k=\langle A_k,M\rangle_F, with $

AkA_k

_{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.

KKK/dK/dDORMPMROCMCDirtyIMCWeightedNN
2700.90N/A0000
3001.00N/A0000
3301.10N/A88000
3601.20N/A99000
3901.30N/A100000
4501.50N/A10044446
5251.75N/A100100100100
6002.00N/A100100100100
7502.50N/A100100100100
9003.00N/A100100100100

Under full Gaussian measurements, PMR achieves 99% success at K=1.2dK=1.2d, while the three convex baselines first reach at least 95% on the tested grid at K=1.75dK=1.75d. This demonstrates PMR's measurement efficiency under Gaussian sensing for the stated experimental setting.

References

  • Chang, G., Zhang, W., and Zhang, L. (2025). Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection. Proceedings of the 42nd International Conference on Machine Learning, 267:7393–7416.
  • Chiang, K.-Y., Hsieh, C.-J., and Dhillon, I. S. (2015). Matrix Completion with Noisy Side Information. Advances in Neural Information Processing Systems, 28.
  • Eftekhari, A., Yang, D., and Wakin, M. B. (2018). Weighted Matrix Completion and Recovery with Prior Subspace Information. IEEE Transactions on Information Theory, 64(6):4044–4071.

W2 / Q1. How robust are DORM and PMR to inexact priors, theoretically and empirically?

To address this concern, we have derived recovery error bounds for both DORM and PMR under inexact subspace priors and conducted corresponding experiments to evaluate their robustness to prior mismatch.

Let M=U1R1+U2R2M=U_1R_1+U_2R_2, with $U=

U1,U2U_1,U_2

$ an orthonormal basis for col⁡(M)\operatorname{col}(M). For the supplied orthonormal prior U~1\widetilde U_1, we define the mismatch between its span col⁡(U~1)\operatorname{col}(\widetilde U_1) and the true column space col⁡(M)=col⁡(U)\operatorname{col}(M)=\operatorname{col}(U) as follows:

=\sin\theta_{\max}\\!\left(\operatorname{col}(\widetilde U_1),\operatorname{col}(M)\right).$$ Thus $\varepsilon$ measures the maximum subspace deviation, and $\varepsilon=0$ exactly when the prior lies within the true column space. Under noiseless measurements, we obtain the following bounds. **DORM recovery error bound under inexact subspace priors.** Write \$M=

M_1,M_2

\$, where $M_1$ contains the first $q=r-r_1$ fully observed columns. DORM estimates the column-space basis by projecting $M_1$ onto the orthogonal complement of $\widetilde U_1$, orthonormalizing the residual, and combining it with the prior: $$\widehat U_2=\operatorname{orth}((I-\widetilde U_1\widetilde U_1^\top)M_1), \qquad \widehat U= �2� .$$ In this estimated basis, the observed block can be expressed exactly as $M_1=\widetilde U_1\widehat R_{11}+\widehat U_2\widehat R_{21}$, where $\widehat R_{11}=\widetilde U_1^\top M_1$ and $\widehat R_{21}=\widehat U_2^\top M_1$. In the second stage, DORM estimates the coefficients of $M_2$ in the basis $\widehat U$. With sensing matrix $G$, the corresponding measurement matrix is $$\widetilde C=G(I_{n-r+r_1}\otimes\widehat U).$$ If the projected block has rank $q$ and $\widetilde C$ has full column rank, then $$\\|\widehat M-M\\|_F \leq \sqrt{1+\frac{\\|G\\|_2^2}{\sigma_{\min}^2(\widetilde C)}} \sqrt{1+\\|\widehat R_{11}\widehat R_{21}^{-1}\\|_2^2} \\,\varepsilon\\,\\|M_2\\|_F.$$ **PMR recovery error bound under inexact subspace priors.** Given the inexact orthonormal prior $\widetilde U_1\in\mathbb R^{m\times r_1}$, choose $\widetilde U_\perp\in\mathbb R^{m\times(m-r_1)}$ as an orthonormal basis for its orthogonal complement. Then \$

\widetilde U_1,\widetilde U_\perp

\$ is orthogonal, and $M$ can be written as $$\begin{aligned} M&=\widetilde U_1\widetilde R_1+\widetilde U_\perp\widetilde X\in\mathbb R^{m\times n},\\\\ \widetilde R_1&=\widetilde U_1^\top M\in\mathbb R^{r_1\times n},\qquad \widetilde X=\widetilde U_\perp^\top M\in\mathbb R^{(m-r_1)\times n}. \end{aligned}$$ Applying the same measurement operator $A\in\mathbb R^{K\times mn}$ gives $$\begin{aligned} y&=A\operatorname{vec}(M) =G_1\operatorname{vec}(\widetilde R_1)+G_2\operatorname{vec}(\widetilde X)\in\mathbb R^K,\\\\ G_1&=A(I_n\otimes\widetilde U_1)\in\mathbb R^{K\times nr_1},\qquad G_2=A(I_n\otimes\widetilde U_\perp)\in\mathbb R^{K\times n(m-r_1)}. \end{aligned}$$ Let $Q_2\in\mathbb R^{K\times(K-nr_1)}$ be an orthonormal basis for $\operatorname{col}(G_1)^\perp$, and let $C_{\mathcal H}$ be the solver stability constant for $\mathcal H(Z)=Q_2^\top G_2\operatorname{vec}(Z)$. Assuming solver stability, $K > nr_1$, and full column rank of $G_1$, the reconstruction error is given by $$\\|\widehat M-M\\|_F \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.$$ With the amplification factors uniformly bounded, both relative recovery errors are $O(\varepsilon)$, and $\varepsilon=0$ gives exact recovery under the respective assumptions. We will include detailed proofs of these error bounds in the revised paper.

W2 / Q1 (continued): Experimental results under inexact subspace priors.

Experimental results. We test Gaussian-generated rank-five matrices M=UR∈R30×50M=UR\in\mathbb R^{30\times50} with noiseless measurements. The prior U1U_1 consists of the first r1=3r_1=3 columns of the orthonormal basis UU. Both methods receive the same perturbed prior,

G_{ij}\overset{\mathrm{iid}}{\sim}\mathcal N(0,1),\qquad \sigma\in\\{10^{-3},10^{-2},10^{-1}\\}.$$ Here $G\in\mathbb R^{30\times3}$ is an independent Gaussian perturbation and $\operatorname{orth}$ uses thin QR. We measure prior mismatch by $$P_\perp=I_{30}-UU^\top,\qquad \varepsilon=\\|P_\perp\widetilde U_1\\|_2=\sin\theta_{\max},$$ where $\theta_{\max}$ is the largest principal angle between the supplied prior and the true column space. The parameter $\sigma$ controls prior perturbation. The table reports the mean $\varepsilon$ and $\theta_{\max}$ at each perturbation level. | Prior perturbation $\sigma$ | Mean $\varepsilon$ | Mean $\theta_{\max}$ (degrees) | | --- | ---: | ---: | | $10^{-3}$ | $5.9472\times10^{-3}$ | 0.340754 | | $10^{-2}$ | $5.9394\times10^{-2}$ | 3.405061 | | $10^{-1}$ | $5.2620\times10^{-1}$ | 31.812107 | To improve robustness to inexact priors, we refine the estimates from both DORM and PMR using ALS. The table reports the median squared relative error $e=\\|\widehat M-M\\|_F^2/\\|M\\|_F^2$ over 500 matched trials at each measurement budget. | $K$ | DORM ($\sigma=10^{-3}$) | PMR ($\sigma=10^{-3}$) | DORM ($\sigma=10^{-2}$) | PMR ($\sigma=10^{-2}$) | DORM ($\sigma=10^{-1}$) | PMR ($\sigma=10^{-1}$) | | ---: | ---: | ---: | ---: | ---: | ---: | ---: | | 300 | $6.800\times10^{-2}$ | $1.556\times10^{0}$ | $6.339\times10^{0}$ | $1.665\times10^{0}$ | $1.142\times10^{2}$ | $3.856\times10^{0}$ | | 350 | $2.456\times10^{-4}$ | $4.966\times10^{-5}$ | $2.584\times10^{-2}$ | $5.055\times10^{-3}$ | $3.014\times10^{0}$ | $2.514\times10^{0}$ | | 400 | $1.000\times10^{-6}$ | $2.669\times10^{-8}$ | $9.507\times10^{-5}$ | $2.759\times10^{-6}$ | $1.260\times10^{0}$ | $9.526\times10^{-1}$ | | 450 | $1.648\times10^{-13}$ | $4.889\times10^{-17}$ | $1.461\times10^{-11}$ | $4.824\times10^{-15}$ | $1.657\times10^{-9}$ | $9.421\times10^{-13}$ | | 500 | $1.967\times10^{-18}$ | $1.369\times10^{-18}$ | $1.972\times10^{-18}$ | $1.372\times10^{-18}$ | $2.107\times10^{-18}$ | $1.412\times10^{-18}$ | These results show that, both DORM and PMR achieve highly accurate recovery despite inexact subspace priors, with PMR generally exhibiting greater robustness to prior mismatch in these experiments. **Q2. Is DORM's full-column observation requirement practical?** Thank you for raising this point. We agree that full-column observations may be unavailable in settings such as live recommender systems. DORM is intended as a constructive demonstration that the theoretical DoF bound is achievable. Our experiments illustrate this attainability under these conditions. For practical settings where full-column observations are unavailable, PMR provides an alternative based on Gaussian measurements without DORM's full-column observation requirement. In particular, the PMR framework is not restricted to a specific measurement scheme and can accommodate general linear measurements $y=\mathcal A(M)$, making it applicable to a broader range of practical settings. In particular, the PMR framework can also be applied to uniformly sampled entry observations in recommender systems, addressing the setting raised by the reviewer. We will clarify DORM's purpose and limitations, and distinguish them from PMR's practical applicability in the revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.