Search papers, labs, and topics across Lattice.
Tsinghua AICASEmoryNJUNortheasternPKUScience & Technology on IntegratedSJTUState Key Laboratory of Complex SystemAug 2, 2026arXiv:2608.00977TIDE-MC introduces a novel GPU framework for matrix completion that leverages Two-Sided Interpolative Decomposition (TSID) to enable efficient processing of billion-scale matrices without exceeding device memory. By using a sampled template submatrix as an anchor, the method allows for scalable computation and storage, significantly reducing both memory usage and reconstruction error. The framework achieves remarkable performance improvements, including up to 11,647x speedup and 99.7% reduction in reconstruction error across 15 benchmarks compared to state-of-the-art methods.
TIDE-MC achieves unprecedented efficiency in matrix completion, handling billion-scale datasets without running out of memory while delivering up to 11,647x speedup.
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.
