Source-linked AI summary
Estimation of high-dimensional low-rank matrices
Angelika Rohde, Alexandre B. Tsybakov
TL;DR
The paper addresses noisy estimation and prediction for high-dimensional matrices whose nominal dimension can exceed the sample size, using low rank as a dimension-reduction assumption. It studies Schatten-p penalized least-squares estimators under restricted-isometry or milder sampling assumptions, obtaining optimal prediction rates up to logarithmic factors and minimax lower bounds in several settings.
Problem
The paper studies how to estimate and predict from a high-dimensional unknown matrix when noisy observations are much fewer than its mT entries, using low-rank structure.
Method
The paper analyzes penalized least-squares Schatten-p estimators for 0 < p ≤ 1 under RI and milder mask assumptions, including matrix completion and multi-task learning.
Results
Schatten-p estimators attain the optimal prediction-error rate up to logarithmic factors, while the paper derives matching minimax lower bounds under RI and for two matrix-completion schemes.
Takeaways & Limitations
Low-rank Schatten estimation achieves near-optimal prediction rates under both restrictive RI conditions and mild mask assumptions in matrix completion and high-dimensional multi-task learning.
Takeaways & Limitations
The mild-assumption result requires singular values not to grow exponentially fast in N and uses p < 1, making the estimator computationally hard.
Abstract
from arXiv · showhide
Suppose that we observe entries or, more generally, linear combinations of entries of an unknown $m\times T$-matrix $A$ corrupted by noise. We are particularly interested in the high-dimensional setting where the number $mT$ of unknown entries can be much larger than the sample size $N$. Motivated by several applications, we consider estimation of matrix $A$ under the assumption that it has small rank. This can be viewed as dimension reduction or sparsity assumption. In order to shrink toward a low-rank representation, we investigate penalized least squares estimators with a Schatten-$p$ quasi-norm penalty term, $p\leq1$. We study these estimators under two possible assumptions---a modified version of the restricted isometry condition and a uniform bound on the ratio "empirical norm induced by the sampling operator/Frobenius norm." The main results are stated as nonasymptotic upper bounds on the prediction risk and on the Schatten-$q$ risk of the estimators, where $q\in[p,2]$. The rates that we obtain for the prediction risk are of the form $rm/N$ (for $m=T$), up to logarithmic factors, where $r$ is the rank of $A$. The particular examples of multi-task learning and matrix completion are worked out in detail. The proofs are based on tools from the theory of empirical processes. As a by-product, we derive bounds for the $k$th entropy numbers of the quasi-convex Schatten class embeddings $S_p^M\hookrightarrow S_2^M$, $p<1$, which are of independent interest.
1. Introduction.
The paper studies noisy estimation of high-dimensional matrices under low-rank structure, using Schatten-p penalized least squares and analyzing prediction and Schatten-q errors. It develops results for general trace regression, matrix completion, and multi-task learning, including optimal prediction rates up to logarithmic factors.
- Trace regression: The trace regression model observes noisy linear combinations of an unknown matrix and aims to estimate it and predict future responses.The design matrices are called masks because they focus on sparse subsets of the matrix entries.
- Applications: Matrix completion and multi-task learning arise from sparse point and column masks, respectively, with matrix completion reconstructing unobserved entries from noisy observations.For d = 1, point masks select individual entries; column masks support a collection of task-specific regression models.
- Motivation: N ≪ mT in matrix completion, making low-rank structure a dimension-reduction assumption for high-dimensional estimation.A rank-r square matrix has (2m − r)r free parameters, of order rm when r ≪ m.
- Estimators: Schatten-p estimators use penalized least squares with a Schatten-p penalty for 0 < p ≤ 1, while p = 1 gives the convex matrix Lasso.The paper studies both prediction error and Schatten-q error for q between p and 2.
- Upper bounds: For p sufficiently close to 0, Schatten-p estimators attain the prediction-error convergence rate rm/N up to logarithmic factors under mild mask assumptions.The result covers matrix completion and high-dimensional multi-task learning when the singular values of A∗ are not exponentially large in N.
- Optimality: Under the RI condition, the prediction-error rate is r max(m,T)/N, and matching minimax lower bounds establish optimality for prediction and Frobenius-norm estimation.The paper also proves lower bounds for collaborative sampling and uniformly sampled matrix completion.
2. Preliminaries.
This section defines the matrix notation, Schatten quasi-norm framework, sampling operator assumptions, and Schatten-p penalized least-squares estimators. It positions the paper’s nonasymptotic estimation and prediction analysis relative to earlier rank-recovery and matrix-Lasso results.
- Notation and Schatten quasi-norms: Matrices are represented through singular values, which define the Schatten quasi-norms used throughout the analysis.The notation introduces rows, columns, singular values, and Schatten spaces for matrices in R^{m×T}.
- Sampling operator: The sampling operator L maps matrices to observed linear measurements, while |L(A−B)|2 defines the induced empirical distance.The masks Xi are generally treated as nonrandom unless explicitly stated otherwise.
- Sampling operator assumptions: Uniform boundedness controls the empirical norm relative to the Frobenius norm, with c0=1 for USR completion and c0=1/N for CS completion.These constants depend on the sampling model and quantify how the operator scales matrix measurements.
- Sampling operator assumptions: The modified restricted-isometry condition RI(r,ν) includes a scaling factor ν to accommodate sparse masks that cannot induce near-unit isometries.The condition is stated for matrices of rank up to r and uses a constant δr∈(0,1).
- Schatten-penalized estimators: Schatten-p estimators minimize penalized least squares for 0<p≤1 and λ>0; p=1 gives the convex matrix Lasso, whereas p<1 is nonconvex.Approximate algorithms for p<1 may find only local minima, while the p=1 problem can be solved efficiently in polynomial time.
- Statistical scope: The paper develops nonasymptotic estimation and prediction bounds meaningful when mT≫N>max(m,T), rather than targeting exact rank recovery.Earlier work considered asymptotic rank recovery for fixed matrix dimensions, while contemporaneous work focused on Frobenius error for the matrix Lasso under matrix restricted isometry.
3. Two schemes of analyzing Schatten estimators.
The paper analyzes Schatten-p estimators through two schemes: one based on the Schatten-p norm of A*, and another based on rank under a restricted isometry condition. Both schemes use an effective noise level, while the second approach can fail for sparse sampling operators.
- The first prediction-error bound depends on the Schatten-p norm of A*, whereas the second depends only on rank but requires the RI condition.
- The analysis controls a stochastic term in a basic inequality, with its difficulty determined by the sampling operator through the effective noise level τ.The estimator uses λ = 4τ, and smaller τ yields faster convergence.
- Under uniform boundedness, USR, and collaborative sampling, Table 1 provides effective-noise-level expressions that determine the resulting convergence rates.The table compares uniformly bounded sampling operators with two matrix-completion schemes.
- For M < N, decreasing p below 1 reduces the generic effective-noise bound, although dedicated analyses can yield sharper rates for USR and collaborative sampling.
- Under RI with ν = 1 and uniform boundedness, the rate is proportional to rM/N for every 0 < p ≤ 1, so p < 1 does not improve convergence.
- Sparse masks make RI poorly suited to matrix completion: when N < mT, a rank-one matrix lies in the sampling operator's null space.For N ≥ mT, RI may hold only when essentially all entries are observed, removing the completion setting.
4. Upper bounds under mild conditions on the sampling operator.
The paper develops upper bounds under the mild uniform boundedness condition on the sampling operator, avoiding dependence on the target matrix's magnitude in rank-based settings. The resulting bounds are presented with high-probability guarantees and are shown to be minimax optimal on corresponding Schatten-p balls under RI.
- The alternative approach requires only the comparatively mild uniform boundedness condition, motivated by settings where RI-based analysis is poorly adapted.
- Theorem 3 analyzes a Schatten-p estimator for Gaussian errors when M > 1, N > eM, rank(A*) ≤ r, and the maximal singular value is bounded.It sets p = (log(N/M))^-1 and provides a high-probability result.
- Theorem 4 gives prediction-risk properties for Schatten-p estimators under Gaussian errors, including a case with 0 < p < 1 and uniform boundedness.
- The bounds in this section hold with probabilities of the form 1 − C exp(−ϑM/C2), with constants independent of r, M, and N.
- The rates are minimax optimal on the corresponding Schatten-p balls for sampling operators satisfying the RI condition.
5. Upper bounds for noisy matrix completion.
The section derives upper bounds for noisy matrix completion using Schatten-1 and nonconvex Schatten-p estimators under USR and collaborative sampling. These bounds attain the rate r max(m,T)/N up to logarithmic factors under different assumptions on A∗.
- USR matrix completion: USR matrix completion bounds apply to Schatten-1 estimators under Bernstein or light-tail noise conditions.The estimators use parameters τ2 or τ3 and λ=4τ2 or λ=4τ3.
- Nonconvex penalty: The nonconvex USR estimator uses p=(log(N/M))^-1 and assumes rank(A∗)≤r and σ1(A∗)≤(N/M)^C∗.Its stated probability guarantee is at least 1−C exp(−ϑM/C2).
- Rates: r max(m,T)/N is achieved up to logarithmic factors under different conditions on the maximal singular value of A∗.The nonconvex result requires a bound on the maximal singular value, while the convex result requires uniform boundedness.
- Collaborative sampling: Collaborative sampling also yields upper bounds for Schatten-1 estimators under Gaussian and Bernstein noise.The Gaussian guarantee is exponential in m+T, while the Bernstein result uses the corresponding τ5 parameter.
- Optimality: The resulting bounds are minimax optimal on the relevant matrix classes under the stated sampling conditions.The section identifies minimax optimality for the bound in (5.4) and discusses a dispersion condition for collaborative sampling.
6. Upper bounds for multi-task learning.
The section applies Schatten estimators to multi-task learning under RI and uniformly bounded sampling operators. It obtains the intrinsic rate rm/N, with logarithm-free bounds in the RI setting, while the broader-dimensional result requires stronger spectral assumptions and a nonconvex penalty.
- RI condition: The RI-based multi-task result covers the computationally easy case p=1 but imposes a strong RI assumption on the masks.The estimator is the Schatten-1 estimator under Gaussian noise and bounded Gram spectra.
- Connections: The low-rank formulation yields corresponding Group Lasso bounds through the block-diagonal nuclear-norm representation.This differs from prior multi-task results that characterize sparsity by the number of nonzero entries in each column.
- Uniformly bounded sampling: The uniformly bounded result applies under bounded Gram spectra and a maximal singular value condition on A∗.It uses p=(log n)^-1 and provides probability at least 1−C exp(−ϑM/C2).
- RI condition: rm/N is the optimal intrinsic dimension/sample size rate, and the RI bounds are free of extra logarithmic factors.Here N=nT in the multi-task formulation.
- Uniformly bounded sampling: The uniformly bounded result remains meaningful when m exceeds each task’s sample size n, provided m≪exp(n).It does not require RI, but assumes singular values of A∗ do not grow exponentially fast and uses computationally hard p<1 penalties.
7. Minimax lower bounds.
The section establishes minimax lower bounds for prediction and Frobenius-norm estimation under RI and for matrix completion sampling schemes. These results match the corresponding upper-bound rates in the stated settings.
- Restricted Isometry: The RI lower bounds show that r max(m,T)/N is minimax optimal for prediction and Schatten-2 estimation on rank-constrained classes.The result extends to intersections of Schatten-0 and Schatten-p balls.
- Restricted Isometry: The lower-bound rates are also minimax optimal on Schatten-p balls under the RI condition in the stated dimensional regime.For m=T=M and m^3>N>m, the lower bound has order (M/N)^(1−p/2), matching the upper bound.
- Matrix completion: The matrix-completion prediction lower bound cannot use the RI condition when N<mT, because RI cannot be satisfied in that regime.For collaborative sampling, the relevant lower bound instead uses the right-hand RI inequality or a dispersion condition.
- Matrix completion: For USR matrix completion, the squared Frobenius estimation lower bound on rank-constrained matrices has order rM/N.The passage identifies this as a lower bound for matrices of rank smaller than r.
- Collaborative sampling: Collaborative-sampling lower bounds are derived under a dispersion condition requiring sufficiently many observations across selected rows or columns.The construction additionally imposes a Frobenius-norm constraint on A∗.
8. Control of the stochastic term.
The section controls the stochastic term through spectral-norm and empirical-process bounds tailored to the sampling design and noise tails. Gaussian concentration can remove logarithmic factors in balanced dimensions, while nonconvex penalties require refined techniques.
- Proof strategies: For p=1, trace duality and spectral-norm bounds control the stochastic term under conditions on the masks and noise.For 0<p<1, the analysis instead uses refined empirical-process techniques.
- General sampling: Gaussian spectral-norm concentration is better when m and T have comparable magnitudes because it avoids extra logarithmic factors.When m≫T, the column version of the alternative lemma can provide a significant improvement.
- USR matrix completion: USR matrix completion receives separate stochastic-term bounds for Bernstein and light-tail noise.For Gaussian noise, the light-tail bound is tighter when N≪(m+T)^2.
- Collaborative sampling: Collaborative-sampling bounds depend on whether masks are distinct and on the geometry of the sampling matrices.The concentration can be exponential or polynomial, and the relevant maximum may be smaller than max(m,T).
- Nonconvex penalties: For 0<p<1, the proof cannot bound Frobenius error by prediction error through RI because the estimator error need not have small rank.Alternative techniques establish an analogous inequality using prediction error instead.
9. Proof of Theorem 2.
The proof of Theorem 2 decomposes the estimation error into structured orthogonal components, then combines restricted isometry and Schatten-norm inequalities to establish the stated bounds. The Schatten-q result is proved first at q=2 and q=p, then extended by interpolation.
- Proof strategy: The error is decomposed into two components, one with rank at most 2r and another orthogonal to the target matrix.The decomposition also makes the two components orthogonal in the trace inner product.
- Proof strategy: For p=1, the proof uses numerical constants from (9.2); the general-p proof has the same structure with different constants.The expressions for general p are described as more cumbersome.
- Proof strategy: A singular-value block decomposition represents the second component as mutually orthogonal matrices grouped by blocks of similarly sized singular values.Each block contains a prescribed number of singular-value indices, ordered from largest to smallest.
- Proof strategy: The proof uses the restricted isometry condition, orthogonality, and Schatten quasi-norm inequalities to control the decomposed error.The argument also uses an inequality specific to 0 < p ≤1 and a rank bound for the first component.
- Conclusion: The Schatten-q bound is established for q=2 and q=p, then extended to every q in [p,2] by Schatten norm interpolation.This interpolation step completes the proof of the q-indexed risk bound.
10. Proofs of the lemmas.
The lemma proofs combine concentration inequalities, covering arguments, and entropy bounds to control random matrix quantities and empirical processes. They also derive uniform Schatten-class bounds under the stated assumptions, with a noted endpoint issue at p=1.
- Concentration lemmas: Random-matrix bounds are obtained by combining net constructions, union bounds, Bernstein-type inequalities, and large-deviation results.The proof refines generic subgaussian bounds using the specific matrix structure to obtain sufficiently accurate rates.
- Concentration lemmas: The proofs separately handle random, deterministic, and matrix-completion-type sampling operators using corresponding concentration arguments.Deterministic designs omit the conditioning event used for random matrices, while self-adjoint dilation supports one matrix-valued bound.
- Entropy and empirical processes: Entropy and empirical-process bounds rely on covering numbers, Schatten-class entropy estimates, and a Hilbert-space concentration lemma.The argument includes peeling and interpolation steps to obtain uniform bounds over the relevant classes.
- Entropy and empirical processes: The entropy integral used in the argument is uniformly bounded when p stays away from 1, but it does not converge at p=1.This is an explicit endpoint limitation of that entropy-integral step.
- Rectangular extension: The rectangular case m ≠ T is reduced to the square case by zero-padding matrices while preserving Schatten norms and sampling inner products.The resulting square-case proof then yields the rectangular result.
11. Entropy numbers for quasi-convex Schatten class embeddings.
This section derives entropy-number bounds for embeddings of quasi-convex Schatten classes, adapting interpolation and factorization techniques to the nonconvex regime p<1. The resulting bounds have linear rather than logarithmic dependence on the matrix dimension.
- Setting: The section derives bounds for the kth entropy numbers of embeddings S_p^M into S_2^M for p<1.Entropy numbers are defined through coverings of the unit ball by norm-radius balls.
- Method: Quasi-norm interpolation and factorization of entropy numbers extend the argument from the S_∞ target to finite S_r targets.The interpolation inequality is applied with parameters relating p and r.
- Main bound: Proposition 1 gives a uniform entropy-number bound for 0 < p < 1 and p < r ≤∞, with an absolute constant independent of p and r.The proof first treats r=∞ and then uses interpolation for finite r.
- Interpretation: The resulting upper bound has linear dependence on M rather than the logarithmic dependence appearing for the ℓ_∞-embedding.This contrast is stated explicitly for the corresponding entropy-number estimates.
- Consequences: Corollary 7 converts the entropy-number result into an entropy bound uniformly over matrix dimension and ε in (0,1].The corollary introduces a positive constant depending on p.