# Near-optimal Rank Adaptive Inference of High Dimensional Matrices

arXiv: https://arxiv.org/abs/2510.08117 · HTML: https://mlsanity.com/paper/2510.08117/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 54 references that are in the map.
- First posted on arXiv 9 Oct 2025.

## Builds on (most cited first, 13 of 13)

- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Non-asymptotic Identification of LTI Systems from a Single Trajectory](https://mlsanity.com/paper/1806.05722/) (2018)
- [Learning Linear Dynamical Systems with Semi-Parametric Least Squares](https://mlsanity.com/paper/1902.00768/) (2019)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Sample Complexity Lower Bounds for Linear System Identification](https://mlsanity.com/paper/1903.10343/) (2019)
- [High-probability minimax lower bounds](https://mlsanity.com/paper/2406.13447/) (2024)
- [Efficient learning of hidden state LTI state space models of unknown order](https://mlsanity.com/paper/2202.01625/) (2022)
- [Adaptive Reduced Rank Regression](https://mlsanity.com/paper/1905.11566/) (2019)
- [Non asymptotic estimation lower bounds for LTI state space models with Cram'er-Rao and van Trees](https://mlsanity.com/paper/2109.08582/) (2021)
- [Learning Low-dimensional Latent Dynamics from High-dimensional Observations: Non-asymptotics and Lower Bounds](https://mlsanity.com/paper/2405.06089/) (2024)
- [Bounds on the geodesic distances on the Stiefel manifold for a family of Riemannian metrics](https://mlsanity.com/paper/2408.07072/) (2024)
- [Simple Relative Deviation Bounds for Covariance and Gram Matrices](https://mlsanity.com/paper/2410.05754/) (2024)

## Abstract (arXiv)

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 instance-specific lower bounds for the sample complexity of such algorithms, uncovering 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 and demonstrate that its performance nearly matches the derived fundamental limits. Our results rely on an enhanced analysis of matrix denoising methods based on singular value thresholding. We validate our findings with applications to multivariate regression and linear dynamical system identification.