Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation

Abstract

In this paper, we consider low rank matrix estimation using either matrix-version Dantzig Selector ${\hat{A}}_{\lambda }^d$ or matrix-version LASSO estimator ${\hat{A}}_{\lambda }^L$. We consider sub-Gaussian measurements, $i.e.$, the measurements $X_1,\dots ,X_n\in {\mathbb{R}}^{m\times m}$ have $i.i.d.$ sub-Gaussian entries. Suppose $\text{rank}(A_0)=r$. We proved that, when $n\ge Cm[r^2\vee r\log (m)\log (n)]$ for some $C>0$, both ${\hat{A}}_{\lambda }^d$ and ${\hat{A}}_{\lambda }^L$ can obtain optimal upper bounds(except some logarithmic terms) for estimation accuracy under spectral norm. By applying metric entropy of Grassmann manifolds, we construct (near) matching minimax lower bound for estimation accuracy under spectral norm. We also give upper bounds and matching minimax lower bound(except some logarithmic terms) for estimation accuracy under Schatten-q norm for every $1\le q\le \infty$. As a direct corollary, we show both upper bounds and minimax lower bounds of estimation accuracy under Ky-Fan-k norms for every $1\le k\le m$.

References in corpus (6)

• The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
• Estimation of high-dimensional low-rank matrices
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Volume Ratio, Sparsity, and Minimaxity under Unitarily Invariant Norms
• Optimal spectral norm rates for noisy low-rank matrix completion

Cited by in corpus (3)

• On Approximating Functions of the Singular Values in a Stream
• Estimation of low rank density matrices by Pauli measurements
• Beyond Symmetry: Best Submatrix Selection for the Sparse Truncated SVD