Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

Abstract

We consider the matrix completion problem under a form of row/column weighted entrywise sampling, including the case of uniform entrywise sampling as a special case. We analyze the associated random observation operator, and prove that with high probability, it satisfies a form of restricted strong convexity with respect to weighted Frobenius norm. Using this property, we obtain as corollaries a number of error bounds on matrix completion in the weighted Frobenius norm under noisy sampling and for both exact and near low-rank matrices. Our results are based on measures of the "spikiness" and "low-rankness" of matrices that are less restrictive than the incoherence conditions imposed in previous work. Our technique involves an $M$-estimator that includes controls on both the rank and spikiness of the solution, and we establish non-asymptotic error bounds in weighted Frobenius norm for recovering matrices lying with ${\ell }_q$-"balls" of bounded spikiness. Using information-theoretic methods, we show that no algorithm can achieve better estimates (up to a logarithmic factor) over these same sets, showing that our conditions on matrices and associated rates are essentially optimal.

References in corpus (6)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Estimation of high-dimensional low-rank matrices
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Consistency of trace norm minimization
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm

Cited by in corpus (147)

• Matrix Completion Methods for Causal Panel Data Models
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
• Geometric median and robust estimation in Banach spaces
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Matrix Completion has No Spurious Local Minimum
• Matrix Completion on Graphs
• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Provable Tensor Factorization with Missing Data
• Noisy low-rank matrix completion with general sampling distribution
• A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Matrix Completion via Max-Norm Constrained Optimization
• RIPless compressed sensing from anisotropic measurements
• Matrix concentration inequalities via the method of exchangeable pairs
• Poisson Matrix Recovery and Completion
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• Canonical Tensor Decomposition for Knowledge Base Completion
• Universal low-rank matrix recovery from Pauli measurements
• Dropping Convexity for Faster Semi-definite Optimization
• Noisy Matrix Completion under Sparse Factor Models
• Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• A Combinatorial Algebraic Approach for the Identifiability of Low-Rank Matrix Completion
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Localization from Incomplete Euclidean Distance Matrix: Performance Analysis for the SVD-MDS Approach
• Exponential Family Matrix Completion under Structural Constraints
• Low Rank Matrix Completion with Exponential Family Noise
• On the Power of Adaptivity in Matrix Completion and Approximation
• Matrix Completion with Deterministic Sampling: Theories and Methods
• Inference for Heterogeneous Effects using Low-Rank Estimation of Factor Slopes
• Probabilistic low-rank matrix completion on finite alphabets
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• Completing Any Low-rank Matrix, Provably
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Collaboratively Learning Preferences from Ordinal Data
• Matrix Completion Under Monotonic Single Index Models
• Practical Matrix Completion and Corruption Recovery using Proximal Alternating Robust Subspace Minimization
• Rank Centrality: Ranking from Pair-wise Comparisons
• Learning Mixed Multinomial Logit Model from Ordinal Data
• Regularization and the small-ball method II: complexity dependent error rates
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
• Recovery guarantee of weighted low-rank approximation via alternating minimization
• Orthogonal Inductive Matrix Completion
• Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• Principal Components and Regularized Estimation of Factor Models
• A General Framework of Dual Certificate Analysis for Structured Sparse Recovery Problems
• Low-rank matrix completion and denoising under Poisson noise
• Non-Convex Matrix Completion Against a Semi-Random Adversary
• Active Target Localization using Low-Rank Matrix Completion and Unimodal Regression
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Learning from Comparisons and Choices
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Sharp recovery bounds for convex demixing, with applications
• Individualized Rank Aggregation using Nuclear Norm Regularization
• High-Dimensional Low-Rank Tensor Autoregressive Time Series Modeling
• Speeding Up Latent Variable Gaussian Graphical Model Estimation via Nonconvex Optimizations
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Proximal Markov chain Monte Carlo algorithms
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Matrix reconstruction with the local max norm
• Unified View of Matrix Completion under General Structural Constraints
• Active Feature Acquisition with Supervised Matrix Completion
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• On the computational and statistical complexity of over-parameterized matrix sensing
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• From bilinear regression to inductive matrix completion: a quasi-Bayesian analysis
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Inference for Heteroskedastic PCA with Missing Data
• On Low-rank Trace Regression under General Sampling Distribution
• Alternating minimization and alternating descent over nonconvex sets
• Matrix Completion and Related Problems via Strong Duality
• Regularized Quantile Regression with Interactive Fixed Effects
• A Minimax Lower Bound for Low-Rank Matrix-Variate Logistic Regression
• Generalized High-Dimensional Trace Regression via Nuclear Norm Regularization
• Optimal tuning-free convex relaxation for noisy matrix completion
• Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• Information-Guided Sampling for Low-Rank Matrix Completion
• Advancing Matrix Completion by Modeling Extra Structures beyond Low-Rankness
• Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data
• Optimal spectral norm rates for noisy low-rank matrix completion
• Learning Markov models via low-rank optimization
• Bayesian Methods in Tensor Analysis
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Flexible Low-Rank Statistical Modeling with Side Information
• Polar Alignment and Atomic Decomposition
• Identifying Influential Entries in a Matrix
• On the Equivalence of Inexact Proximal ALM and ADMM for a Class of Convex Composite Programming
• Estimation of low rank density matrices by Pauli measurements
• Noisy Inductive Matrix Completion Under Sparse Factor Models
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
• AutoGFI: Streamlined Generalized Fiducial Inference for Modern Inference Problems in Models with Additive Errors
• Low rank estimation of smooth kernels on graphs
• Joint Estimation and Inference for Multi-Experiment Networks of High-Dimensional Point Processes
• Matrix Completion via Nonconvex Regularization: Convergence of the Proximal Gradient Algorithm
• Poisson Matrix Completion
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Concentration for matrix martingales in continuous time and microscopic activity of social networks
• Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information
• Consistent Collective Matrix Completion under Joint Low Rank Structure
• Statistical Inference for High-Dimensional Linear Regression with Blockwise Missing Data
• HOSVD-Based Algorithm for Weighted Tensor Completion
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Low-rank matrix estimation in multi-response regression with measurement errors: Statistical and computational guarantees
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
• Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion; Some Statistical and Algorithmic Theory for Adaptive-Impute
• Tight Risk Bound for High Dimensional Time Series Completion
• Self-Reflective Terrain-Aware Robot Adaptation for Consistent Off-Road Ground Navigation
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
• TenIPS: Inverse Propensity Sampling for Tensor Completion
• Approximate Factor Models with Strongly Correlated Idiosyncratic Errors
• Active Matrix Factorization for Surveys
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• Fast Nonconvex SDP Solvers for Large-scale Power System State Estimation
• Learning Parameters for Weighted Matrix Completion via Empirical Estimation
• Error Analysis on Graph Laplacian Regularized Estimator
• The CP-matrix completion problem
• Multi-sample estimation of centered log-ratio matrix in microbiome studies
• Rank-Constrained Least-Squares: Prediction and Inference
• Deconvolution with Unknown Error Distribution Interpreted as Blind Isotonic Regression
• Causal Discovery in High-Dimensional Point Process Networks with Hidden Nodes
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Convergence rate of Bayesian tensor estimator: Optimal rate without restricted strong convexity
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion
• Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization
• A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
• Nonparametric Estimation of Low Rank Matrix Valued Function
• Outliers Detection in Networks with Missing Links
• Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction
• Matrix Completion for Survey Data Prediction with Multivariate Missingness
• Matrix optimization based Euclidean embedding with outliers
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers
• Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms