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 · 649 citations
Engineering · Mathematics · #Advanced SAR Imaging Techniques #Applied mathematics #Combinatorics #Eigenvalues and eigenvectors #Estimator #Logarithm #Mathematical analysis #Mathematical optimization #Mathematics #Matrix (chemical analysis) #Matrix completion #Matrix norm #Minimax #Numerical methods in inverse problems #Rank (graph theory) #Rate of convergence #Sparse and Compressive Sensing Techniques #Statistics #Upper and lower bounds #math.ST #msc:60B20 #msc:60G15 #msc:62H12 #msc:62J99 #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.1011.6256

published in arXiv (Cornell University) (Cornell University)

arxiv created 2016/03/23 · arxiv updated 2016/03/24

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 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 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
• Support recovery and sup-norm convergence rates for sparse pivotal estimation
• 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
• Optimal spectral norm rates for noisy low-rank matrix completion
• Projection-Free Algorithms in Statistical Estimation
• Confidence Intervals for Low-Dimensional Parameters in High-Dimensional Linear Models
• Conformal Network Link Prediction with False Discovery Rate Control under Unstructured Missingness
• Generalized Co-sparse Factor Regression
• Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Transfer Learning for Matrix Completion
• Fusing heterogeneous data sets
• Structured Matrix Completion with Applications to Genomic Data Integration
• Provable Tensor-Train Format Tensor Completion by Riemannian Optimization
• Worst possible sub-directions in high-dimensional models
• How well can we learn large factor models without assuming strong factors?
• Blind Deconvolution using Convex Programming
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• A General Framework of Dual Certificate Analysis for Structured Sparse Recovery Problems
• First-Order Sparse Convex Optimization: Better Rates with Sparse Updates
• Optimal Estimation of Low Rank Density Matrices
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• Localized Complexities for Transductive Learning
• Estimation of matrices with row sparsity
• Time Matters: Multi-scale Temporalization of Social Media Popularity
• Sparse spectral estimation with missing and corrupted measurements
• Inference for Heterogeneous Effects using Low-Rank Estimation of Factor Slopes
• Fourier Low-rank and Sparse Tensor for Efficient Tensor Completion
• Reduced rank regression via adaptive nuclear norm penalization
• Adaptive Estimation of Noise Variance and Matrix Estimation via USVT Algorithm
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Trust, but verify: benefits and pitfalls of least-squares refitting in high dimensions
• Deconvolution with Unknown Error Distribution Interpreted as Blind Isotonic Regression
• Lasso and probabilistic inequalities for multivariate point processes
• Regularization parameter selection for low rank matrix recovery
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion; Some Statistical and Algorithmic Theory for Adaptive-Impute
• Reduced-rank Regression in Sparse Multivariate Varying-Coefficient Models with High-dimensional Covariates
• Regularization-free estimation in trace regression with symmetric positive semidefinite matrices
• A pseudo-RIP for multivariate regression
• High-dimensional estimation with geometric constraints
• Matrix completion based on Gaussian parameterized belief propagation
• Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
• Matrix Completion Methods for Causal Panel Data Models
• Computational Efficient and Minimax Optimal Nonignorable Matrix Completion
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Leveraging Shared Factor Structures for Enhanced Matrix Completion with Nonconvex Penalty Regularization
• Hierarchical Convex Optimization by the Hybrid Steepest Descent Method with Proximal Splitting Operators—Enhancements of SVM and Lasso

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