Near-optimal Rank Adaptive Inference of High Dimensional Matrices

Frédéric Zheng, Yassir Jedra, Alexandre Proutiere
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3232-3240, 2026.

Abstract

We address the problem of estimating a high-dimensional matrix from linear measurements, with a focus on designing optimal rank-adaptive algorithms. These algorithms infer the matrix by estimating its singular values and the corresponding singular vectors up to an effective rank, adaptively determined based on the data. We establish, for the first time, instance-specific lower bounds for the sample complexity of such algorithms. We uncover fundamental trade-offs in selecting the effective rank: balancing the precision of estimating a subset of singular values against the approximation cost incurred for the remaining ones. Our analysis identifies how the optimal effective rank depends on the matrix being estimated, the sample size, and the noise level. We propose an algorithm that combines a Least-Squares estimator with a universal singular value thresholding procedure. We provide finite-sample error bounds for this algorithm, that are tighter than those of existing rank-adaptive algorithms. Furthermore, our bounds nearly match the derived fundamental limits. Finally, we confirm experimentally that our algorithm outperforms existing rank-adaptive algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-zheng26a, title = { Near-optimal Rank Adaptive Inference of High Dimensional Matrices }, author = {Zheng, Fr{\'e}d{\'e}ric and Jedra, Yassir and Proutiere, Alexandre}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3232--3240}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/zheng26a/zheng26a.pdf}, url = {https://proceedings.mlr.press/v300/zheng26a.html}, abstract = { We address the problem of estimating a high-dimensional matrix from linear measurements, with a focus on designing optimal rank-adaptive algorithms. These algorithms infer the matrix by estimating its singular values and the corresponding singular vectors up to an effective rank, adaptively determined based on the data. We establish, for the first time, instance-specific lower bounds for the sample complexity of such algorithms. We uncover fundamental trade-offs in selecting the effective rank: balancing the precision of estimating a subset of singular values against the approximation cost incurred for the remaining ones. Our analysis identifies how the optimal effective rank depends on the matrix being estimated, the sample size, and the noise level. We propose an algorithm that combines a Least-Squares estimator with a universal singular value thresholding procedure. We provide finite-sample error bounds for this algorithm, that are tighter than those of existing rank-adaptive algorithms. Furthermore, our bounds nearly match the derived fundamental limits. Finally, we confirm experimentally that our algorithm outperforms existing rank-adaptive algorithms. } }
Endnote
%0 Conference Paper %T Near-optimal Rank Adaptive Inference of High Dimensional Matrices %A Frédéric Zheng %A Yassir Jedra %A Alexandre Proutiere %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-zheng26a %I PMLR %P 3232--3240 %U https://proceedings.mlr.press/v300/zheng26a.html %V 300 %X We address the problem of estimating a high-dimensional matrix from linear measurements, with a focus on designing optimal rank-adaptive algorithms. These algorithms infer the matrix by estimating its singular values and the corresponding singular vectors up to an effective rank, adaptively determined based on the data. We establish, for the first time, instance-specific lower bounds for the sample complexity of such algorithms. We uncover fundamental trade-offs in selecting the effective rank: balancing the precision of estimating a subset of singular values against the approximation cost incurred for the remaining ones. Our analysis identifies how the optimal effective rank depends on the matrix being estimated, the sample size, and the noise level. We propose an algorithm that combines a Least-Squares estimator with a universal singular value thresholding procedure. We provide finite-sample error bounds for this algorithm, that are tighter than those of existing rank-adaptive algorithms. Furthermore, our bounds nearly match the derived fundamental limits. Finally, we confirm experimentally that our algorithm outperforms existing rank-adaptive algorithms.
APA
Zheng, F., Jedra, Y. & Proutiere, A.. (2026). Near-optimal Rank Adaptive Inference of High Dimensional Matrices . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3232-3240 Available from https://proceedings.mlr.press/v300/zheng26a.html.

Related Material