Pith. sign in

REVIEW 4 major objections 5 minor 73 references

TIDE-MC: Two-Sided Interpolative Decomposition for Billion-Scale GPU Matrix Completion

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A sampled template submatrix, recovered in GPU memory and extended chunk-by-chunk, is claimed to make billion-scale matrix completion fit on a single GPU.

desk verdict The bounded-memory chunked pipeline is a plausible systems idea, but the headline numbers and implementation description don't hold up as written. read the letter →

arxiv 2608.00977 v1 pith:VJABUGJL submitted 2026-08-02 cs.DC

Chengying Huan , Yubo Wang , Pinhuan Wang , Lizheng Chen , Jie Zhang , Fangxin Liu , Qing Wang , Ruixuan Liu
show 6 more authors
Shaonan Ma Mingxing Zhang Zhibin Wang Rong Gu Guihai Chen Chen Tian
This is my paper
classification cs.DC
keywords matrixcompletiontwo-sidedinterpolativedecompositionGPUboundedmemorytemplatesubmatrixlow-rankfactorizationmixedprecisionstochasticgradientdescentpipelinedALS
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that matrix completion at billion scale can run on a single GPU without ever storing the full matrix on device, by first recovering a small sampled template submatrix and then reconstructing the rest column-chunk by column-chunk from it. The load-bearing claim is Two-Sided Interpolative Decomposition: an exact-rank skeleton identity that lets a well-conditioned template stand in for the whole low-rank component. On this basis TIDE-MC reports completing MovieLens, Netflix, and Yahoo! Music workloads that crash whole-matrix GPU solvers, with up to 11,647x speedup, up to 8.5x lower peak memory, and up to 99.7% lower reconstruction error in its benchmarks. The paper is explicit that TSID is a systems abstraction for reducing resident memory, not a standalone recovery guarantee.

What carries the argument

Two-Sided Interpolative Decomposition (TSID), an exact-rank skeleton/CUR identity that lets a well-conditioned sampled template submatrix serve as an algebraic anchor: the full rank-$k$ component is recovered as $W_L R^*_k W_R^T$. Around this identity TIDE-MC builds a two-stage template-extension pipeline: Stage I uses conflict-free hierarchical SGD-based regularized matrix factorization to recover the template, and Stage II uses chunked, double-buffered ALS-style least-squares extension with an asymmetric gradient-clipping guardrail for stable FP16 Tensor Core execution.

What would settle it

Take a synthetic matrix whose low-rank structure is concentrated on a small fraction of columns, e.g., $R=U\Sigma V^T$ with $V$ having nonzero entries only in 1% of its rows, sample the template with the paper's default $\alpha=0.1$ uniform column sampling, run TIDE-MC, and compare NMAE against a leverage-score-sampled template of the same size. If the uniform-template NMAE degrades by more than an order of magnitude relative to the reported 0.0027 level while the leverage-sampled template stays near it, the random-anchor assumption behind TSID fails on skewed column structure.

Watch

Extended reading notes

Core claim

The paper's central claim is a skeleton identity: with the SVD $R=U\Sigma V^T$ and selected row/column index sets $I,J$ such that the core $R^*_k=(R_k)_{I,J}$ is nonsingular, the matrices $W_L=U_1(U_1(I,:))^{-1}$ and $W_R=V_1(V_1(J,:))^{-1}$ satisfy $W_L R^*_k W_R^T = R_k$, so the sampled template exactly reconstructs the ideal rank-$k$ component. TIDE-MC's engineering claim is that this identity can be turned into a bounded-memory GPU scheme: recover the template submatrix by regularized matrix factorization (Stage I), hold it fixed, and reconstruct the rest of the matrix chunk-by-chunk with least-squares extension (Stage II), with resident GPU memory $O(k(1+\alpha)n+|\Omega_{\$\Delta$ c}|+k\D

Load-bearing premise

The load-bearing premise is that a uniformly random 10% column sample of a sparse, approximately low-rank matrix captures the dominant row and column subspaces well enough that recovering the template and extending it by least squares gives the reported accuracy; no recovery guarantee covers non-uniform column structure.

Editorial extensions

If this is right

  • Whole-matrix residency is no longer required: the GPU working set becomes the template factors plus one active chunk, so matrices whose full form exceeds HBM become completable on a single 40GB A100.
  • Workloads that crash existing GPU solvers—MovieLens 25M, MovieLens Latest 33M, Netflix Prize, and Yahoo! Music—are completed by TIDE-MC, with reported NMAE of 0.1352, 0.1385, 0.1382, and 0.1473, respectively.
  • On the evaluated benchmarks TIDE-MC reports up to 11,647x speedup against NN-centric baselines, up to 1,377x against SVD-centric baselines, up to 8.5x lower peak GPU memory, and up to 99.7% lower NMAE.
  • Mixed-precision Tensor Core execution is made stable by asymmetric gradient clipping, which caps positive gradient growth while allowing shrinkage, preventing FP16 overflow on power-law data.
  • Stage II's double-buffered chunk pipeline hides PCIe latency, and distributing chunks across multiple GPUs scales runtime down with modest overhead.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper: the template-anchor scheme is a general resource-reduction primitive; the same two-stage structure could be applied to other memory-bound low-rank computations, such as kernel ridge regression over tall-skinny matrices or streaming SVD, wherever a well-sampled submatrix can anchor the column space.
  • Beyond the paper: the uniform-random sampling choice is the least defended part of the design; a leverage-score or rank-revealing sampling strategy could replace it inside the same framework and likely improve robustness on nonuniform column structure, at the cost of the negligible overhead Table 3 reports for heavier samplers.
  • Beyond the paper: the reported real-dataset NMAEs (0.135–0.147) are modest, so the practical case for TIDE-MC on recommendation workloads rests on speed and memory, not on beating tuned baselines at accuracy; a direct comparison on identical holdout splits with hyperparameter-tuned baselines would clarify that trade-off.
  • Beyond the paper: the asymmetric clipping guardrail is a self-contained numerical technique that could transfer to other mixed-precision SGD workloads, such as embedding tables or factorization machines, where power-law gradients cause FP16 overflow.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes TIDE-MC, a bounded-memory GPU framework for matrix completion based on a Two-Sided Interpolative Decomposition (TSID) abstraction. The claimed contribution is a two-stage pipeline: Stage I recovers a randomly sampled template submatrix via a conflict-free parallel SGD-based RMF kernel; Stage II reconstructs the full matrix by chunked ALS with PCIe/computation overlap, stabilized by asymmetric gradient clipping for mixed precision. The evaluation reports up to 11,647x speedup, 8.5x lower peak memory, and up to 99.7% lower reconstruction error compared with five baselines, and reports completion of MovieLens 25M/33M, Netflix, and Yahoo! Music workloads that cause baselines to OOM.

Significance. If the results are reproducible and the algorithmic reduction is sound, the idea of using a sampler submatrix as a resident template to decouple logical matrix size from GPU working set is a potentially useful systems contribution for large-scale matrix completion. The ablation study (Figure 7) and multi-GPU scaling (Figure 8) are informative, and the paper is honest in Section 6.9 about the limitation that the template itself must fit in GPU memory. However, the central claims are not supported as stated: the headline speedups are computed only on small matrices where baselines run, the large-scale results have no baselines because of OOM, the described implementation stack cannot execute the kernel that is claimed to provide the Stage I speedups, and the TSID identity is not actually instantiated by the system. No code is shipped, so the experimental results are not independently verifiable.

major comments (4)
  1. [Section 5.1 vs. Section 6 (Implementation)] The conflict-free synchronization engine is described in terms of warp shuffle instructions, shared-memory block-level reductions, and 'at most one atomic per block.' Section 6 states the implementation is ~7,000 lines of Python, uses PyTorch AMP and CUDA 12.4, and that 'all tensor operations... run on GPU.' PyTorch's Python API does not expose warp-shuffle or custom block-reduction primitives; realizing the described kernel requires a custom CUDA/C++ extension, which is neither mentioned nor shipped. This is a load-bearing gap because the claimed Stage I performance is attributed to this mechanism.
  2. [Section 3.1 and Sections 4-5] Theorem 1 is a two-sided ID identity that reconstructs the ideal rank-k component as W_L R* W_R^T. The implementation, however, samples only columns and never forms W_L or W_R; Stage II solves a least-squares problem conditioned on the recovered template. Thus the 'TSID-guided' decomposition is not the computation whose performance is measured. The paper does not explain how Theorem 1 supports the actual one-sided template-extension scheme, leaving the algebraic anchor decoupled from the system design.
  3. [Table 5 and Section 6.2] On MovieLens 25M/33M, Netflix, and Yahoo! Music, all external baselines OOM, so the reported runtime and NMAE values for TIDE-MC have no comparator. The abstract's claims of 'up to 11,647x speedup, 8.5x lower peak memory, and 99.7% lower reconstruction error' are supported only on small matrices (1Kx3K, 3Kx3K). The large-scale results demonstrate that the system runs, but they do not quantify the claimed advantage over state-of-the-art baselines at billion scale; the evaluation conflates 'completes workloads' with 'outperforms baselines on those workloads.'
  4. [Section 3.2 'Practical Approximation Error' and Section 5.1 'Sampling'] The error bound for the template-extension scheme is ∥bR-R∥_F ≤ ∥E∥_F + ∥W_L∥∥W_R∥(∥bR*-R*∥_F + ∥E_{I,J}∥_F), where bR* is the empirical template recovery and E_{I,J} is the residual of the sampled submatrix. No theorem or quantitative guarantee is provided that random column sampling with α=0.1 preserves the dominant row/column subspace sufficiently for the extension to reach the reported NMAE on power-law, partially observed data. The evidence is limited to Table 3 and one sensitivity plot; this is the key assumption behind the system's accuracy and it is unsupported in the manuscript.
minor comments (5)
  1. [Table 5] The parenthetical speedup factors, e.g., '21.40K (8136x)', are not defined in the table caption; clarify that the number in parentheses is TIDE-MC's speedup over that baseline, and ensure the base time is read consistently.
  2. [Section 6.7] The text says NMAE 'rises to 3.2×' on 100K×150K, but NMAE is a scalar error metric; a multiplier is ambiguous. Also, Figure 10 appears to show NMAE around 2.4, which is inconsistent with the NMAE values around 0.13 in Table 5; please specify the exact metric and axis.
  3. [Equation (5)] The p_j update in Equation (5) is not normalized while the q_i update is normalized by 1/n. This asymmetry is not justified. If intentional, explain why it is needed for convergence or stability.
  4. [Section 6.1] The sentence 'Image Construction and Noise Clear support an image reconstruction and denoising case study' is grammatically awkward; clarify that these are the datasets used in the case study.
  5. [Section 6.9] The limitation is acknowledged that the template must fit in GPU memory. Given that this is a central boundary of the claimed scalability, the discussion would benefit from stating for which of the tested datasets the template approaches the memory limit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the TSID identity is an acknowledged exact-rank skeleton/CUR identity, not a predictive derivation; all empirical claims are measured on held-out test entries against external baselines.

full rationale

The paper's central algebraic step (Theorem 1) is an identity by construction: W_L and W_R are defined as U1(U1(I,:))^{-1} and V1(V1(J,:))^{-1}, so rand rand = R_k is a direct substitution. The paper itself labels it 'an exact-rank skeleton/CUR identity' (Section 3.1) and explicitly disclaims that it is 'an end-to-end proof of optimal sparse matrix completion,' so the identity is not presented as a derived empirical prediction. The practical error bound in Section 3.2 is a genuine decomposition of error into residual ||E||, interpolation norms, template recovery error, and sampled-residual error; it is not a renamed fit. Hyperparameters (α, ξ, chunk count) are tuned, but the reported NMAE is computed on a held-out test set Ωtest (Section 6.1), so no fitted value is renamed as a prediction. The evaluation is against external baselines (CSNN, CSPGD, CGM, MVGMC, NTK) and real datasets; no load-bearing claim relies on self-citation or on a uniqueness theorem imported from the authors. The admitted limitations—template residency in Section 6.9 and possible degradation under nonuniform missingness in Section 6.8—are scope/robustness caveats, not circular dependencies. No circular step can be exhibited with a specific equation reducing a claimed prediction to its input.

Assumptions & free parameters 6 free parameters · 4 assumptions · 0 invented entities

The central pipeline rests on the low-rank prior, the sufficiency of random column sampling, the recoverability of the template from sparse observations, and template residency in HBM. The system introduces no new scientific entities, but it relies on several hand-tuned hyperparameters (alpha, chunk count, xi, lambda, eta) that are not justified by a validation protocol.

free parameters (6)
  • template sampling ratio alpha = 0.1 (large), 0.5 (small)
    Controls template size and thus memory and accuracy; tuned per dataset. Section 6.1 Parameter Selection.
  • chunk count = 10 (default), range 10-30
    Determines Stage II parallelism and memory; tuned per dataset in Section 6.8.
  • gradient clipping threshold xi = 0.1
    Hand-set; improves convergence and accuracy in mixed precision. Section 5.3.
  • latent rank k = not reported (approximately alpha*n in Table 1)
    Ranks of P and Q in Stage I; not specified for each experiment.
  • regularization lambda and learning rate eta = not reported
    Hyperparameters for RMF and ALS objectives (Equations 2, 6) and Adam; exact values or schedules not given.
  • iteration counts t1, t2 = not reported
    Convergence stopping criteria not specified.
assumptions (4)
  • domain assumption The target matrix is approximately low-rank
    Standard assumption for matrix completion; stated in Section 1.
  • ad hoc to paper Random column sampling with ratio alpha preserves the dominant row and column subspace sufficiently
    Load-bearing assumption for Stage II accuracy; supported only by Table 3 empirical evidence, no theoretical guarantee for the sparse case.
  • domain assumption The estimated template bR* fits in GPU HBM
    Explicitly stated in Section 6.9 as a limitation; all evaluated workloads satisfy it.
  • domain assumption The observed template entries suffice to recover the full template rows via RMF
    Even sparse template observations must yield accurate dense factors P and Q; no recovery guarantee is proven.

how reviews work

0 comments
Cite this review

Pith. "Pith review of TIDE-MC: Two-Sided Interpolative Decomposition for Billion-Scale GPU Matrix Completion." pith.science (2026). https://pith.science/paper/VJABUGJL

@misc{pith2026260800977,
  author       = {Pith},
  title        = {Pith review of: TIDE-MC: Two-Sided Interpolative Decomposition for Billion-Scale GPU Matrix Completion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VJABUGJL}},
  note         = {Machine review of arXiv:2608.00977}
}
read the original abstract

Matrix completion supports large-scale recommendation and scientific computing, yet existing GPU solvers commonly assume that the observed matrix or its dense factors fit in device memory. On real workloads, this assumption leads to out-of-memory failures or severe PCIe overhead under naive paging. We present TIDE-MC, a bounded-memory GPU framework built on Two-Sided Interpolative Decomposition (TSID). TSID uses a sampled template submatrix as an anchor for reconstructing the full low-rank matrix, allowing computation and storage to scale with the template and active data chunks rather than the complete matrix. TIDE-MC realizes this formulation through two execution stages. First, a conflict-free synchronization engine recovers the template using parallel factorization and hierarchical gradient aggregation. Second, a chunked reconstruction pipeline extends the recovered template to the remaining matrix while overlapping PCIe transfers with GPU computation. An asymmetric gradient-clipping scheme stabilizes mixed-precision Tensor Core execution. Across 15 benchmarks, TIDE-MC completes workloads that cause existing GPU solvers to run out of memory. Compared with the evaluated state-of-the-art baselines, it achieves up to 11,647x speedup, reduces peak memory usage by up to 8.5x, and lowers reconstruction error by up to 99.7%. These results show that template-anchored decomposition and stage-specific GPU execution can scale matrix completion beyond device-memory capacity.

Figures

Figures reproduced from arXiv: 2608.00977 by the authors.

Figure 1
Figure 1. Workflow of NN-centric and SVD-centric matrix completion methods, both requiring the full matrix to reside in device memory during execution. solves 𝑅b= arg min 𝑋 ∈R𝑛1×𝑛2 ∥𝑋 ∥∗ s.t. RΩ(𝑋 − 𝑅) = 0, where ∥𝑋 ∥∗ denotes the nuclear norm and RΩ retains ob￾served entries. This problem can be formulated as a semidef￾inite program [42, 45] and is often solved by singular value thresholding (SVT) [7], which iteratively appl… view at source ↗
Figure 2
Figure 2. Overall workflow of TIDE-MC: submatrix sampling and recovery (Stage I) and chunk-based ALS reconstruction (Stage II). side the sampled template. The submatrix is parameterized as 𝑅b∗ ≈ 𝑃𝑄⊤, with 𝑃 ∈ R 𝑚×𝑘 and 𝑄 ∈ R 𝛼𝑛×𝑘 , by solving min 𝑃,𝑄 ∑︁ (𝑗,𝑖) ∈Ω∗ [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Stage I as a conflict-free engine: sparse RMF up￾dates are aggregated and mapped onto Tensor Core tiles. the dominant computations as matrix multiplications Δ𝐽 = MatMul(𝑃, 𝑄). Tensor Cores perform FP16 multiplications with FP32 accumulation, providing high throughput without sacrificing accuracy. We implement this kernel in PyTorch using Automatic Mixed Precision (AMP), which manages loss scaling and precision trans… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Stage II as a roofline-driven pipelined dataflow engine: ALS compute on chunk 𝑖 overlaps with prefetch of 𝑖 + 1 and flush of 𝑖 − 1. dient clipping as a numerical stabilization guardrail that en￾ables aggressive mixed-precision computation without sacri￾ficing the conve…
Figure 5
Figure 5. Figure 5: Comparison of loss over iterations with and with￾out gradient clipping (threshold 𝜉). 7,000 lines of Python. Using PyTorch’s device management, inputs are automatically moved to the target device, so all ten￾sor operations in parallel SGD and ALS routines run on GPU. T…
Figure 6
Figure 6. Figure 6: Qualitative comparison for image denoising [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 9
Figure 9. Figure 9: Time and accuracy comparison: RMF vs. SVD. 10K×100K 50K×100K 100K×100K 100K×150K 0 100 200 300 400 500 Matrix Size Time (s) Time 0 1 2 3 4 NMAE Accuracy [PITH_FULL_IMAGE:figures/full_fig_p011_9.png]
Figure 8
Figure 8. Figure 8: Performance comparison under different hardware configurations. execution time across all matrix sizes, with larger benefits on bigger matrices. For example, it cuts runtime on a 1K×3K matrix from 8.3s to 4.71s, with up to a 43% reduction overall. Efficiency of Opt2. O…
Figure 11
Figure 11. Figure 11: Sampling ratio and chunk number sensitivity. scale. 6.8 Parameter Sensitivity Effect of Subcolumn Sampling Ratio. The subcolumn sampling ratio determines the proportion of columns se￾lected during Stage I. As shown in [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

73 extracted references · 49 canonical work pages

  1. [1]

    Association for Computing Machinery, New York, NY, USA

    2011.HetRec ’11: Proceedings of the 2nd International Workshop on In- formation Heterogeneity and Fusion in Recommender Systems(Chicago, Illinois). Association for Computing Machinery, New York, NY, USA

    work page 2011

  2. [2]

    Hervé Abdi. 2006. Singular Value Decomposition ( SVD ) and Generalized Singular Value Decomposition ( GSVD ).https://api. semanticscholar.org/CorpusID:8786634

    work page 2006

  3. [3]

    Derin Babacan, Martin Luessi, Rafael Molina, and Aggelos K

    S. Derin Babacan, Martin Luessi, Rafael Molina, and Aggelos K. Kat- saggelos. 2012. Sparse Bayesian Methods for Low-Rank Matrix Esti- mation.IEEE Transactions on Signal Processing60, 8 (2012), 3964–3977. https://doi.org/10.1109/TSP.2012.2197748

    work page arXiv 2012

  4. [4]

    Dheeraj Baby and Soumyabrata Pal. 2024. Online Matrix Comple- tion: A Collaborative Approach with Hott Items. InProceedings of the 41st International Conference on Machine Learning (Proceedings of Ma- chine Learning Research, Vol. 235), Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkam...

    work page 2024

  5. [5]

    James Bennett and Stan Lanning. 2007. The netflix prize. (2007).https://www.cs.uic.edu/~liub/KDD-cup-2007/proceedings/ The-Netflix-Prize-Bennett.pdf

    work page 2007

  6. [6]

    Lee, and Devavrat Shah

    Christian Borgs, Jennifer Chayes, Christina E. Lee, and Devavrat Shah

    work page

  7. [7]

    Candès, and Zuowei Shen

    Jian-Feng Cai, Emmanuel J. Candès, and Zuowei Shen. 2010. A Singular Value Thresholding Algorithm for Matrix Completion.SIAM Journal on Optimization20, 4 (2010), 1956–1982.https://doi.org/10.1137/ 080738970arXiv:https://doi.org/10.1137/080738970

    doi:10.1137/080738970 2010

  8. [8]

    Tony Cai, and Anru Zhang

    Tianxi Cai, T. Tony Cai, and Anru Zhang. 2016. Structured Matrix Com- pletion with Applications to Genomic Data Integration.J. Amer. Statist. Assoc.111, 514 (2016), 621–633.https://doi.org/10.1080/01621459.2015. 1021005arXiv:https://doi.org/10.1080/01621459.2015.1021005 PMID: 28042188

    arXiv 2016

Show all 73 references
  1. [9]

    Candès and Benjamin Recht

    Emmanuel J. Candès and Benjamin Recht. 2009. Exact matrix comple- tion via convex optimization.Foundations of Computational Mathe- matics9, 6 (2009), 717–772.https://doi.org/10.1007/s10208-009-9045-5

    2009 doi

  2. [10]

    Feilong Cao, Miaomiao Cai, and Yuanpeng Tan. 2015. Image Interpo- lation via Low-Rank Matrix Completion and Recovery.IEEE Transac- tions on Circuits and Systems for Video Technology25, 8 (2015), 1261– 1270.https://doi.org/10.1109/TCSVT.2014.2372351

    2015

  3. [11]

    Eric C Chi, Hua Zhou, Guo-Kang Chen, Diego O Del Vecchyo, and Kenneth Lange. 2013. Genotype imputation via matrix completion. Genome Research23, 3 (2013), 509–518.https://doi.org/10.1101/gr. 145821.112

    2013 doi

  4. [12]

    Davide Chicco, Matthijs J Warrens, and Giuseppe Jurman. 2021. The co- efficient of determination R-squared is more informative than SMAPE, MAE, MAPE, MSE and RMSE in regression analysis evaluation.Peerj computer science7 (2021), e623.https://doi.org/10.7717/peerj-cs.623

    2021 doi

  5. [13]

    Stephen Chou, Fredrik Kjolstad, and Saman Amarasinghe. 2018. For- mat abstraction for sparse tensor algebra compilers.Proc. ACM Pro- gram. Lang.2, OOPSLA, Article 123 (Oct. 2018), 30 pages.https: //doi.org/10.1145/3276493

    2018 doi

  6. [14]

    Evgenia Chunikhina, Raviv Raich, and Thinh Nguyen. 2014. Perfor- mance analysis for matrix completion via iterative hard-thresholded SVD. In2014 IEEE Workshop on Statistical Signal Processing (SSP). 392– 395.https://doi.org/10.1109/SSP.2014.6884658

    2014

  7. [15]

    Clarkson

    Kenneth L. Clarkson. 2010. Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm.ACM Trans. Algorithms6, 4, Article 63 (Sept. 2010), 30 pages.https://doi.org/10.1145/1824777.1824783

    2010

  8. [16]

    Chenjiao Feng, Jiye Liang, Peng Song, and Zhiqiang Wang. 2020. A fusion collaborative filtering method for sparse data in recommender systems.Inf. Sci.521, C (June 2020), 365–379.https://doi.org/10.1016/ j.ins.2020.02.052

    2020

  9. [17]

    Haas, and Yannis Sismanis

    Rainer Gemulla, Erik Nijkamp, Peter J. Haas, and Yannis Sismanis

  10. [18]

    Golub and Charles F

    Gene H. Golub and Charles F. van Loan. 1980. An Analysis of the Total Least Squares Problem.SIAM J. Numer. Anal.17, 6 (1980), 883–893. https://doi.org/10.1137/0717073arXiv:https://doi.org/10.1137/0717073

    1980 doi

  11. [19]

    Yuzhou Gu, Zhao Song, Junze Yin, and Licheng Zhang. 2023. Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time.ArXivabs/2302.11068 (2023).https://api.semanticscholar. org/CorpusID:257079026

    2023 arXiv

  12. [20]

    Xin Guan, Chang-Tsun Li, and Yu Guan. 2017. Matrix Factorization With Rating Completion: An Enhanced SVD Model for Collaborative Filtering Recommender Systems.IEEE Access5 (2017), 27668–27678. https://doi.org/10.1109/ACCESS.2017.2772226

    2017

  13. [21]

    Yu Gui, Rina Barber, and Cong Ma. 2023. Conformalized matrix com- pletion. InThirty-seventh Conference on Neural Information Processing Systems.https://openreview.net/forum?id=6f320HfMeS

    2023

  14. [22]

    Maxwell Harper and Joseph A

    F. Maxwell Harper and Joseph A. Konstan. 2015. The MovieLens Datasets: History and Context.ACM Trans. Interact. Intell. Syst.5, 4, Article 19 (Dec. 2015), 19 pages.https://doi.org/10.1145/2827872

    2015 doi

  15. [23]

    Trevor Hastie, Rahul Mazumder, Jason D Lee, and Reza Zadeh. 2015. Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares.Journal of machine learning research : JMLR16 (2015), 3367—3402.https://europepmc.org/articles/PMC6530939

    2015

  16. [24]

    Yao Hu, Debing Zhang, Jieping Ye, Xuelong Li, and Xiaofei He. 2013. Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization.IEEE Transactions on Pattern Analysis and Machine Intelligence35, 9 (2013), 2117–2130.https://doi.org/10.1109/TPAMI. 2012.271

    2013 doi

  17. [25]

    Arnav Kapur, Kshitij Marwah, and Gil Alterovitz. 2016. Gene expres- sion prediction using low-rank matrix completion.BMC Bioinformat- ics17, 1 (2016), 243.https://doi.org/10.1186/s12859-016-1106-6

    2016 doi

  18. [26]

    Petr Kasalicky, Antoine Ledent, and Rodrigo Alves. 2023. Uncertainty- adjusted Inductive Matrix Completion with Graph Neural Networks. InProceedings of the 17th ACM Conference on Recommender Systems (Singapore, Singapore)(RecSys ’23). Association for Computing Ma- chinery, New...

    2023

  19. [27]

    Keshavan, Andrea Montanari, and Sewoong Oh

    Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh

  20. [28]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. 2017. Adam: A Method for Sto- chastic Optimization. arXiv:1412.6980 [cs.LG]https://arxiv.org/abs/ 1412.6980

    2017 arXiv

  21. [29]

    Arezou Koohi and Houman Homayoun. 2019. Parallel Multi-View Graph Matrix Completion for Large Input Matrix. In2019 IEEE 9th Annual Computing and Communication Workshop and Conference (CCWC). IEEE, Las Vegas, NV, USA, 337–341.https://dblp.org/rec/ conf/ccwc/KoohiH19

    2019

  22. [30]

    Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factor- ization techniques for recommender systems.Computer42, 8 (2009), 30–37.https://doi.org/10.1109/MC.2009.263

    2009 doi

  23. [31]

    Antonina Krajewska and Ewa Niewiadomska-Szynkiewicz. 2024. Ef- ficient Data Completion and Augmentation. In2024 IEEE 11th Inter- national Conference on Data Science and Advanced Analytics (DSAA). 1–10.https://doi.org/10.1109/DSAA61799.2024.10722793

    2024

  24. [32]

    Antonina Krajewska and Ewa Niewiadomska-Szynkiewicz. 2026. Ran- domized Approach to Matrix Completion: Applications in Recommen- dation Systems and Image Inpainting.Machine Learning115, 3 (2026), 1–32.https://doi.org/10.1007/s10994-026-06995-2

    2026 doi

  25. [33]

    Jiaxuan Li, Xiaoyan Zhu, Hongrui Wang, Yu Zhang, Xin Lai, and Jiayin Wang. 2025. Multi-Label Ranking Loss Minimization for Matrix Com- pletion.Proceedings of the AAAI Conference on Artificial Intelligence39, 17 (Apr. 2025), 18333–18340.https://doi.org/10.1609/aaai.v39i17.34017

    2025 doi

  26. [34]

    Andersen, Jun Woo Park, Alexander J

    Mu Li, David G. Andersen, Jun Woo Park, Alexander J. Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J. Shekita, and Bor-Yiing Su. 2014. Scaling Distributed Machine Learning with the Parameter Server. InProceedings of the 11th USENIX Symposium on Operating Systems Desig...

    2014

  27. [35]

    Gangmuk Lim, Jeongseob Ahn, Wencong Xiao, Youngjin Kwon, and Myeongjae Jeon. 2021. Zico: Efficient GPU Memory Sharing for Con- current DNN Training. In2021 USENIX Annual Technical Conference (USENIX ATC 21). USENIX Association, 161–175.https://www.usenix. org/conference/atc21/...

    2021

  28. [36]

    Canyi Lu, Changbo Zhu, Chunyan Xu, Shuicheng Yan, and Zhouchen Lin. 2015. Generalized Singular Value Thresholding.Proceedings of the AAAI Conference on Artificial Intelligence29, 1 (Feb. 2015).https: //doi.org/10.1609/aaai.v29i1.9464

    2015 doi

  29. [37]

    Aanchal Mongia, Debarka Sengupta, and Angshul Majumdar. 2019. McImpute: Matrix Completion Based Imputation for Single Cell RNA- seq Data.Frontiers in GeneticsVolume 10 - 2019 (2019).https://doi. org/10.3389/fgene.2019.00009

    2019

  30. [38]

    Arvind Narayanan and Vitaly Shmatikov. 2008. Robust De- anonymization of Large Sparse Datasets. In2008 IEEE Symposium on Security and Privacy (sp 2008). 111–125.https://doi.org/10.1109/SP. 2008.33

    2008 doi

  31. [39]

    Devanur, Gregory R

    Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R. Devanur, Gregory R. Ganger, Phillip B. Gibbons, and Matei Zaharia. 2019. PipeDream: generalized pipeline parallelism for DNN training. InProceedings of the 27th ACM Symposium on Operating Systems Princ...

    2019

  32. [40]

    Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGres- ley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, Amar Phanishayee, and Matei Zaharia. 2021. Efficient large-scale language model training on GPU cl...

    2021

  33. [42]

    2000.Semidefinite Pro- gramming Relaxations of Nonconvex Quadratic Optimization

    Yuri Nesterov, Henry Wolkowicz, and Yinyu Ye. 2000.Semidefinite Pro- gramming Relaxations of Nonconvex Quadratic Optimization. Springer US, Boston, MA, 361–419.https://doi.org/10.1007/978-1-4615-4381- 7_13

    2000 doi

  34. [43]

    Netflix. 2006. Netflix Prize Dataset.https://www.netflixprize.com/. https://www.netflixprize.com/Accessed: 2025-04-14

    2006

  35. [44]

    Uroš Ocepek, Jože Rugelj, and Zoran Bosnić. 2015. Improving matrix factorization recommendations for examples in cold start.Expert Systems with Applications42, 19 (2015), 6784–6794.https://doi.org/10. 1016/j.eswa.2015.04.071

    2015

  36. [45]

    Pablo A. Parrilo. 2003. Semidefinite programming relaxations for semialgebraic problems.Mathematical Programming96, 2 (May 2003), 293–320.https://doi.org/10.1007/s10107-003-0387-5

    2003 doi

  37. [46]

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Ed- ward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, L...

    2019

  38. [47]

    2000.The Geometry of Semidefinite Programming

    Gábor Pataki. 2000.The Geometry of Semidefinite Programming. Springer US, Boston, MA, 29–65.https://doi.org/10.1007/978-1-4615- 4381-7_3

    2000 doi

  39. [48]

    Adityanarayanan Radhakrishnan, George Stefanakis, Mikhail Belkin, and Caroline Uhler. 2022. Simple, fast, and flexible framework for matrix completion with infinite width neural networks.Proceedings of the National Academy of Sciences119, 16 (2022), e2115064119.https: //doi.or...

    2022 doi

  40. [49]

    Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He

  41. [50]

    Soheil Sadeghi Eshkevari and Shamim N. Pakzad. 2020. Signal Re- construction from Mobile Sensors Network Using Matrix Completion Approach. InTopics in Modal Analysis & Testing, Volume 8, Michael L. Mains and Brandon J. Dilworth (Eds.). Springer International Publish- ing, Cham...

    2020 doi

  42. [51]

    Angela Serra, Pietro Coretto, Michele Fratello, and Roberto Tagli- aferri. 2017. Robust and sparse correlation matrix estimation for the analysis of high-dimensional genomics data.Bioinformatics 34, 4 (10 2017), 625–634.https://doi.org/10.1093/bioinformatics/ btx642arXiv:https...

    2017 doi

  43. [52]

    Shin, Peder E

    Peter J. Shin, Peder E. Z. Larson, Michael A. Ohliger, Michael Elad, John M. Pauly, Daniel B. Vigneron, and Michael Lustig. 2014. Calibra- tionless parallel imaging reconstruction based on structured low-rank matrix completion.Magnetic Resonance in Medicine72, 4 (2014), 959– 9...

    2014 doi

  44. [53]

    Min Tao and Xiaoming Yuan. 2011. Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations. SIAM Journal on Optimization21, 1 (2011), 57–81.https://doi.org/10. 14 1137/100781894arXiv:https://doi.org/10.1137/100781894

    2011 doi

  45. [54]

    Christina Teflioudi, Evangelos Makari, and Rainer Gemulla. 2012. Dis- tributed matrix completion. In2012 IEEE 12th International Conference on Data Mining. IEEE, 655–664.https://doi.org/10.1109/ICDM.2012. 120

    2012 doi

  46. [55]

    Adrien Todeschini, François Caron, and Marie Chavent. 2013. Proba- bilistic Low-Rank Matrix Completion with Adaptive Spectral Regu- larization Algorithms. InAdvances in Neural Information Processing Systems. 845–853.https://proceedings.neurips.cc/paper_files/paper/ 2013/file/5...

    2013

  47. [56]

    Firas Trabelsi, David Vilar, Mara Finkelstein, and Markus Freitag

  48. [57]

    Hoi-To Wai, Jean Lafond, Anna Scaglione, and Eric Moulines. 2017. Decentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems.IEEE Trans. Automat. Control62, 11 (2017), 5522–5537. https://doi.org/10.1109/TAC.2017.2685559

    2017

  49. [58]

    Olsen, Andrew R

    Jialei Wang, Peder A. Olsen, Andrew R. Conn, and Aurelie C. Lozano

  50. [59]

    Zaiwen Wen, Wotao Yin, and Yin Zhang. 2012. Solving a Low-Rank Factorization Model for Matrix Completion by a Nonlinear Successive Over-Relaxation Algorithm.Mathematical Programming Computation 4, 4 (2012), 333–361.https://doi.org/10.1007/s12532-012-0044-1

    2012 doi

  51. [60]

    2013.The cuda handbook: A comprehensive guide to gpu programming

    Nicholas Wilt. 2013.The cuda handbook: A comprehensive guide to gpu programming. Pearson Education.https://www.cudahandbook.com/

    2013

  52. [61]

    Wencong Xiao, Romil Bhardwaj, Ramachandran Ramjee, Muthian Si- vathanu, Nipun Kwatra, Zhenhua Han, Pratyush Patel, Xuan Peng, Hanyu Zhao, Quanlu Zhang, Fan Yang, and Lidong Zhou. 2018. Gan- diva: Introspective Cluster Scheduling for Deep Learning. In13th USENIX Symposium on Op...

    2018

  53. [62]

    Kun Xie, Xiaocan Li, Xin Wang, Gaogang Xie, Jigang Wen, and Dafang Zhang. 2019. Active Sparse Mobile Crowd Sensing Based on Matrix Completion. InProceedings of the 2019 International Conference on Management of Data(Amsterdam, Netherlands)(SIGMOD ’19). As- sociation for Comput...

    2019

  54. [63]

    Zikai Xiong, Yimin Wei, Renjie Xu, and Yanwei Xu. 2022. Low-rank traffic matrix completion with marginal information.J. Comput. Appl. Math.410 (2022), 114219.https://doi.org/10.1016/j.cam.2022.114219

    2022

  55. [64]

    Yahoo. 2023. Yahoo Research Outreach Dataset.https://www.yahoo. com/research/outreach-dataset.https://www.yahoo.com/research/ outreach-datasetAccessed: 2025-04-14

    2023

  56. [65]

    Haishan Ye, Ziang Zhou, Luo Luo, and Tong Zhang. 2020. Decentral- ized Accelerated Proximal Gradient Descent. InAdvances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Had- sell, M.F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 18308–1...

    2020

  57. [66]

    Yuanhang Yu, Dong Wen, Ying Zhang, Xiaoyang Wang, Wenjie Zhang, and Xuemin Lin. 2021. Efficient Matrix Factorization on Heteroge- neous CPU-GPU Systems. In2021 IEEE 37th International Confer- ence on Data Engineering (ICDE). 1871–1876.https://doi.org/10.1109/ ICDE51399.2021.00169

    2021

  58. [67]

    Xing, Joseph E

    Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Eric P. Xing, Joseph E. Gonzalez, and Ion Stoica. 2022. Alpa: Automat- ing Inter- and Intra-Operator Parallelism for Distributed Deep Learn- ing. In16th US...

    2022

  59. [68]

    Oliver Zier, Rahul Kannan, Aaron Smith, Mark Vogelsberger, and Erkin Verbeek. 2024. Adapting arepo-rt for exascale computing: GPU acceleration and efficient communication.Monthly Notices of the Royal Astronomical Society533, 1 (2024), 268–286.https://doi.org/10.1093/ mnras/stae1837 15

    2024

  60. [2010]

    Matrix completion from a few entries.IEEE Transactions on Information Theory56, 6 (2010), 2980–2998.https://doi.org/10.1109/ TIT.2010.2046205

    2010

  61. [2011]

    InProceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

    Large-scale matrix factorization with distributed stochastic gradient descent. InProceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 69–77. https://doi.org/10.1145/2020408.2020426

  62. [2016]

    InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).https://doi.org/10.1109/CVPR.2016

    Removing Clouds and Recovering Ground Observations in Satellite Image Sequences via Temporally Contiguous Robust Matrix Completion. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).https://doi.org/10.1109/CVPR.2016. 301

    2016 doi

  63. [2017]

    InProceedings of the 31st International Conference on Neural Information Processing Systems(Long Beach, California, USA) (NIPS’17)

    Thy friend is my friend: iterative collaborative filtering for sparse matrix estimation. InProceedings of the 31st International Conference on Neural Information Processing Systems(Long Beach, California, USA) (NIPS’17). Curran Associates Inc., Red Hook, NY, USA, 4718–4729. ht...

  64. [2020]

    InSC20: International Conference for High Performance Computing, Networking, Storage and Analysis

    ZeRO: Memory optimizations Toward Training Trillion Param- eter Models. InSC20: International Conference for High Performance Computing, Networking, Storage and Analysis. 1–16.https://doi.org/ 10.1109/SC41405.2020.00024

    2020 arXiv

  65. [2024]

    InAdvances in Neural Information Processing Systems, A

    Efficient Minimum Bayes Risk Decoding using Low-Rank Matrix Completion Algorithms. InAdvances in Neural Information Processing Systems, A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (Eds.), Vol. 37. Curran Associates, Inc., 54714– 54733.http...

    doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.