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

2014/03/25 by Dong Xia, Xia, Dong
Computer Science · Engineering · Mathematics · #Advanced Image Processing Techniques #FOS: Computer and information sciences #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1403.6499

openalex publication_date 2014/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider low rank matrix estimation using either matrix-version Dantzig Selector A_λ^d or matrix-version LASSO estimator A_λ^L. We consider sub-Gaussian measurements, i.e., the measurements X₁,…,X_n∈ℝ^{m× m} have i.i.d. sub-Gaussian entries. Suppose \textrmrank(A₀)=r. We proved that, when n≥ Cm[r²\vee rlog(m)log(n)] for some C>0, both A_λ^d and A_λ^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≤ q≤∞. As a direct corollary, we show both upper bounds and minimax lower bounds of estimation accuracy under Ky-Fan-k norms for every 1≤ k≤ m.

Citations

• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Stable signal recovery from incomplete and inaccurate measurements
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion

Related

• Optimal Estimation of Schatten Norms of a rectangular Matrix
• Estimation of low rank density matrices: bounds in Schatten norms and other distances
• Optimal Estimation of Low Rank Density Matrices
• Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
• Fundamental limits of low-rank matrix estimation: the non-symmetric case