Abstract
In this work, we focus on the high-dimensional trace regression model with a low-rank coefficient matrix. We establish a nearly optimal in-sample prediction risk bound for the rank-constrained least-squares estimator under no assumptions on the design matrix. Lying at the heart of the proof is a covering number bound for the family of projection operators corresponding to the subspaces spanned by the design. By leveraging this complexity result, we perform a power analysis for a permutation test on the existence of a low-rank signal under the high-dimensional trace regression model. We show that the permutation test based on the rank-constrained least-squares estimator achieves non-trivial power with no assumptions on the minimum (restricted) eigenvalue of the covariance matrix of the design. Finally, we use alternating minimization to approximately solve the rank-constrained least-squares problem to evaluate its empirical in-sample prediction risk and power of the resulting permutation test in our numerical study.
Introduction
A central challenge in high-dimensional statistics is the recovery of hidden low-rank structures from limited, noisy observations. The prevailing approach, nuclear-norm regularization, offers computational efficiency through convexity but relies heavily on the Restricted Eigenvalue (RE) property of the design matrix. In practice, features are frequently collinear, causing these conditions to fail and undermining the reliability of convex estimators.
This paper investigates the rank-constrained least-squares estimator, the matrix-valued counterpart to "best subset selection." Although non-convex and computationally demanding, this estimator demonstrates superior statistical robustness. We show that it achieves nearly optimal prediction performance without requiring restrictive assumptions on the design matrix, making it a powerful tool for analyzing complex, highly correlated datasets.
The Trace Regression Model
The study focuses on the trace regression model, where a response vector $y \in \mathbb{R}^n$ is generated according to:
$$y_i = \langle X_i, \Theta^* \rangle + \epsilon_i, \quad i = 1, \dots, n$$
where $X_i$ are feature matrices, $\Theta^*$ is a low-rank coefficient matrix, and $\epsilon_i$ is noise. The rank-constrained least-squares estimator seeks to minimize the residual sum of squares subject to $\text{rank}(\Theta) \le r$.
As illustrated in Figure 1, the problem can be viewed through the lens of matrix factorizations. When one factor (e.g., $V^*$) is fixed, the relationship between the features and the response can be linearized, forming a design matrix $X_{V^*}$ where each row is a vectorized product $\text{vec}(X_i V^*)$. This transformation is central to algorithms like Alternating Minimization (AM), which the authors use to find approximate solutions.
Theoretical Contributions
Complexity via Algebraic Geometry
To establish prediction risk bounds, we must quantify the "complexity" of the space of low-rank projection matrices. We employ tools from real algebraic geometry—specifically the work of Basu, Pollack, and Coste-Roy—to calculate the covering number of these subspaces. This geometric approach allows us to bound the complexity of the estimator's search space more tightly than traditional methods.
Robustness to Collinearity
A key finding is that the rank-constrained estimator achieves an in-sample prediction risk of $O(rd \log(n) / n)$ with zero assumptions on the design matrix. Unlike nuclear-norm methods, it remains effective even when features are perfectly correlated, consistently identifying the best low-rank approximation.
Inference and Permutation Testing
For inference—deciding if a signal actually exists—the authors propose a permutation test. This method shuffles the response data to construct a null distribution, avoiding reliance on complex asymptotic distributions that may not hold in high dimensions.
We demonstrate "super-efficiency" at the origin: when no signal exists (the true matrix is zero), the testing rates can be faster than the standard $n^{-1/2}$ because the null model occupies a low-complexity point in the parameter space. Furthermore, the test is tuning-parameter free; a rank-1 permutation test remains powerful even if the underlying signal has a higher rank (e.g., rank-4).
Numerical Evaluation
The theory was verified using synthetic datasets under various conditions:
- Gaussian Design: A standard compressed sensing setup with independent Gaussian features.
- Matrix Completion: "One-hot" feature matrices simulating the classic problem of filling in missing entries in a large table.
- Signal-to-Noise Ratio (SNR) Variations: Testing performance across a wide range of SNRs.
In high SNR regimes, the rank-constrained estimator (via AM) consistently outperformed nuclear-norm (NN) regularization. Crucially, the permutation test maintained the correct Type I error rate (false positive rate) across all settings, whereas convex methods often struggled with overfitting during cross-validation for the tuning parameter $\lambda$.
Conclusion and Future Work
The rank-constrained least-squares estimator provides a robust alternative to convex regularization in high-dimensional settings where design assumptions are likely to be violated. While the non-convex nature of the problem presents computational challenges, the statistical advantages—particularly the lack of reliance on the RE condition—are significant.
Future work will focus on extending these "assumption-free" results to out-of-sample generalization and refining non-convex optimization algorithms to make this approach even more practical for massive-scale datasets.
Summary updated