Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion

2010/11/29 by Vladimir Koltchinskii, Koltchinskii, Vladimir, Alexandre B. Tsybakov +3 · 58 citations
Engineering · Mathematics · #Sparse and Compressive Sensing Techniques #Numerical methods in inverse problems #Advanced SAR Imaging Techniques

paper · pdf · doi:10.48550/arxiv.1011.6256

Abstract

This paper deals with the trace regression model where n entries or linear\ncombinations of entries of an unknown m₁\× m₂ matrix A₀ corrupted by\nnoise are observed. We propose a new nuclear norm penalized estimator of A₀\nand establish a general sharp oracle inequality for this estimator for\narbitrary values of n,m₁,m₂ under the condition of isometry in expectation.\nThen this method is applied to the matrix completion problem. In this case, the\nestimator admits a simple explicit form and we prove that it satisfies oracle\ninequalities with faster rates of convergence than in the previous works. They\nare valid, in particular, in the high-dimensional setting m₁m₂\≫ n. We\nshow that the obtained rates are optimal up to logarithmic factors in a minimax\nsense and also derive, for any fixed matrix A₀, a non-minimax lower bound on\nthe rate of convergence of our estimator, which coincides with the upper bound\nup to a constant factor. Finally, we show that our procedure provides an exact\nrecovery of the rank of A₀ with probability close to 1. We also discuss the\nstatistical learning setting where there is no underlying model determined by\nA₀ and the aim is to find the best trace regression model approximating the\ndata.\n

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Cited by

• Tight convex relaxations for sparse matrix factorization
• Estimation bounds and sharp oracle inequalities of regularized\n procedures with Lipschitz loss functions
• Simultaneous Heterogeneity and Reduced-rank Learning for Multivariate Response Regression
• Detecting Latent Communities in Network Formation Models
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Optimal link prediction with matrix logistic regression
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• On the properties of variational approximations of Gibbs posteriors
• Tensor Kernel Recovery for Spatio-Temporal Hawkes Processes
• Debiasing Stochastic Gradient Descent to handle missing values
• Latent space models for grouped multiplex networks
• Random perturbation of low rank matrices: Improving classical bounds
• Learning Markov models via low-rank optimization
• Robust Reduced Rank Regression
• Millimeter Wave Channel Estimation via Exploiting Joint Sparse and Low-Rank Structures
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Leveraging Diversity and Sparsity in Blind Deconvolution
• Outlier-robust sparse/low-rank least-squares regression and robust\n matrix completion
• A generalised log-determinant regularizer for online semi-definite programming and its applications
• Low-Rank Spatial Channel Estimation for Millimeter Wave Cellular Systems
• On the computational and statistical complexity of over-parameterized matrix sensing
• Structured functional regression models for high-dimensional spatial spectroscopy data
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• High-dimensional low-rank matrix regression with unknown latent structures
• Regularization and the small-ball method II: complexity dependent error rates
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Selective Factor Extraction in High Dimensions
• Near-optimal Rank Adaptive Inference of High Dimensional Matrices
• Generalized simultaneous component analysis of binary and quantitative data
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection
• Data fusion using factor analysis and low-rank matrix completion
• Matrix Completion for Survey Data Prediction with Multivariate Missingness
• A General Decision Theory for Huber's ε-Contamination Model
• Graph Structure Learning for Robust Graph Neural Networks
• A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
• Optimal Bias-variance Tradeoff in Matrix and Tensor Estimation
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Image Segmentation Using Subspace Representation and Sparse\n Decomposition
• Recovery Performance of PhaseLift for Phase Retrieval from Coded Diffraction Patterns
• Estimation of low rank density matrices: bounds in Schatten norms and other distances
• Adaptive Reduced Rank Regression
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• An Overview on the Estimation of Large Covariance and Precision Matrices
• From Blind deconvolution to Blind Super-Resolution through convex\n programming
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion
• Breaking the 1/√(n) Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• High dimensional regression and matrix estimation without tuning parameters
• High-dimensional regression with unknown variance
• Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation
• Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction
• Some exercises with the Lasso and its compatibility constant
• Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion
• Factor Models for High-Dimensional Tensor Time Series

Related

• Optimal spectral norm rates for noisy low-rank matrix completion
• Low Rank Matrix Completion with Exponential Family Noise
• Rank penalized estimators for high-dimensional matrices
• On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
• Sharp oracle inequalities for the prediction of a high-dimensional matrix