Near-optimal Rank Adaptive Inference of High Dimensional Matrices

• URL: http://arxiv.org/abs/2510.08117v1
• Date: Thu, 09 Oct 2025 12:01:46 GMT
• Title: Near-optimal Rank Adaptive Inference of High Dimensional Matrices
• Authors: Frédéric Zheng, Yassir Jedra, Alexandre Proutiere,
• Abstract summary: We address the problem of estimating a high-dimensional matrix from linear measurements.<n>We propose an algorithm that combines a Least-Squares estimator with a universal singular value thresholding procedure.<n>Our results rely on an enhanced analysis of matrix denoising methods based on singular value thresholding.
• Score: 46.66027208538566
• License: http://creativecommons.org/licenses/by/4.0/
• 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 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.

Related papers

• Principled Algorithms for Optimizing Generalized Metrics in Binary Classification [53.604375124674796]
  We introduce principled algorithms for optimizing generalized metrics, supported by $H$-consistency and finite-sample generalization bounds.<n>Our approach reformulates metric optimization as a generalized cost-sensitive learning problem.<n>We develop new algorithms, METRO, with strong theoretical performance guarantees.
  arXiv  Detail & Related papers  (2025-12-29T01:33:42Z)
• Matrix Completion via Residual Spectral Matching [2.677354612516629]
  Noisy matrix completion has attracted significant attention due to its applications in recommendation systems, signal processing and image restoration.<n>We propose a novel residual spectral matching criterion that incorporates the numerical but also locational information of residuals.<n>We derive optimal statistical properties by analyzing the spectral properties of sparse random matrices and bounding the effects of low-rank perturbations and partial observations.
  arXiv  Detail & Related papers  (2024-12-13T09:42:42Z)
• Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise [8.032235780123429]
  We study the problem of estimating a rank one signal matrix from an observed matrix generated by corrupting the signal with additive rotationally invariant noise.<n>We develop a new class of approximate message-passing algorithms for this problem and provide a simple and concise characterization of their dynamics in the high-dimensional limit.
  arXiv  Detail & Related papers  (2024-05-28T11:42:51Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms [9.245687221460654]
  Motivated by applications in single-cell biology and metagenomics, we investigate the problem of matrixing based on a noisy monotone Toeplitz matrix model. We establish fundamental statistical limit for this problem in a decision-theoretic framework and demonstrate that a constrained least squares rate. To address this, we propose a novel-time adaptive sorting algorithm with guaranteed performance improvement.
  arXiv  Detail & Related papers  (2022-01-17T14:53:52Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)
• Boosting Algorithms for Estimating Optimal Individualized Treatment Rules [4.898659895355356]
  We present nonparametric algorithms for estimating optimal individualized treatment rules. The proposed algorithms are based on the XGBoost algorithm, which is known as one of the most powerful algorithms in the machine learning literature.
  arXiv  Detail & Related papers  (2020-01-31T22:26:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.