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

2007/06/28 by Benjamin Recht, Maryam Fazel, Pablo A. Parrilo · 3,628 citations
Computer Science · Engineering · Mathematics · #Affine transformation #Algorithm #Blind Source Separation Techniques #Combinatorics #Compressed sensing #Indoor and Outdoor Localization Technologies #Linear map #Mathematical optimization #Mathematics #Matrix norm #Minification #Pure mathematics #Rank (graph theory) #Restricted isometry property #Sparse and Compressive Sensing Techniques #math.OC #math.ST #msc:15A52 #msc:90C25 #msc:90C59 #stat.TH

paper · pdf · doi:10.1137/070697835

published in SIAM Review 52(3), 471-501 (Society for Industrial and Applied Mathematics)

arxiv created 2007/06/28 · openalex publication_date 2010/01/01 · arxiv updated 2010/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the literature of a diverse set of fields including system identification and control, Euclidean embedding, and collaborative filtering. Although specific instances can often be solved with specialized algorithms, the general affine rank minimization problem is NP-hard because it contains vector cardinality minimization as a special case. In this paper, we show that if a certain restricted isometry property holds for the linear transformation defining the constraints, the minimum-rank solution can be recovered by solving a convex optimization problem, namely, the minimization of the nuclear norm over the given affine space. We present several random ensembles of equations where the restricted isometry property holds with overwhelming probability, provided the codimension of the subspace is sufficiently large. The techniques used in our analysis have strong parallels in the compressed sensing framework. We discuss how affine rank minimization generalizes this preexisting concept and outline a dictionary relating concepts from cardinality minimization to those of rank minimization. We also discuss several algorithmic approaches to minimizing the nuclear norm and illustrate our results with numerical examples.

Citations

• The Approximation of One Matrix by Another of Lower Rank
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins
• Least angle regression
• Local Minima and Convergence in Low-Rank Semidefinite Programming
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Stable signal recovery from incomplete and inaccurate measurements
• Semidefinite Programming
• Compressed sensing

Cited by

• Stability of Low-Rank Implicit Regularization in Perturbed Deep Matrix Factorization
• Causal Inference for Sequential Settings under Interference and Latent Confounding
• Kurdyka-Łojasiewicz exponent via inf-projection
• Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
• Solving Partial Differential Equations on Manifolds From Incomplete Inter-Point Distance
• Speeding up finite-time consensus via minimal polynomial of a weighted graph - a numerical approach
• High-Dimensional Dynamic Systems Identification with Additional Constraints
• An Efficient Primal-Dual Prox Method for Non-Smooth Optimization
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices
• Speaker diarization with session-level speaker embedding refinement using graph neural networks
• Shape and Spatially-Varying Reflectance Estimation From Virtual Exemplars
• Primal-Dual Interior-Point Methods for Domain-Driven Formulations
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• On the subdifferential of symmetric convex functions of the spectrum for symmetric and orthogonally decomposable tensors
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Stable Blind Deconvolution over the Reals from Additional Autocorrelations
• Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
• State-Of-The-Art Algorithms For Low-Rank Dynamic Mode Decomposition
• Large-Scale Convex Minimization with a Low-Rank Constraint
• Large-scale Kernel-based Feature Extraction via Budgeted Nonlinear Subspace Tracking
• Defect Detection by MIMO Wireless Sensing based on Weighted Low-Rank\n plus Sparse Recovery
• The Gram dimension of a graph
• Low-Rank Matrix Recovery from Row-and-Column Affine Measurements
• A Geometric Approach to Low-Rank Matrix Completion
• Schatten-p Quasi-Norm Regularized Matrix Optimization via Iterative Reweighted Singular Value Minimization
• Nuclear norm penalization and optimal rates for noisy low rank matrix\n completion
• When Bayesian Tensor Completion Meets Multioutput Gaussian Processes: Functional Universality and Rank Learning
• Phase-space entropy at acquisition reflects downstream learnability
• Moving Object Detection by Detecting Contiguous Outliers in the Low-Rank Representation
• Social Trust Prediction via Max-norm Constrained 1-bit Matrix Completion
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Scalable Plug-and-Play ADMM with Convergence Guarantees
• Simultaneous Heterogeneity and Reduced-rank Learning for Multivariate Response Regression
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Multi-weight Matrix Completion with Arbitrary Subspace Prior Information
• Group-Structured Adversarial Training
• Linear models based on noisy data and the Frisch scheme
• Gray Box Identification of State-Space Models Using Difference of Convex Programming
• Dynamic matrix recovery from incomplete observations under an exact low-rank constraint
• Sampling and reconstructing signals from a union of linear subspaces
• Residual-Weighted Decomposition of Positive Operators
• A Differentiable Measure of Algebraic Complexity: Provably Exact Discovery of Group Structures
• Low-Rank and Low-Order Decompositions for Local System Identification
• Enhancing the Spatio-temporal Observability of Grid-Edge Resources in Distribution Grids
• Note on sampling without replacing from a finite collection of matrices
• Optimizing the Driving Profile for Vehicle Mass Estimation -- extended version
• A Simpler Approach to Matrix Completion
• Phase Recovery, MaxCut and Complex Semidefinite Programming
• A problem dependent analysis of SOCP algorithms in noisy compressed sensing
• Variational Analysis of the Ky Fan k-norm
• Constrained Shadow Tomography for Molecular Simulation on Quantum Devices
• Stochastic Iterative Hard Thresholding for Low-Tucker-Rank Tensor Recovery
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent
• Parameter Recovery from Tangential Interpolations for Systems with an LFT Structure
• Solving exact and noisy rank-one tensor completion with semidefinite programming
• Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training
• Atomic norm denoising with applications to line spectral estimation
• Proximal Markov chain Monte Carlo algorithms
• Linear Matrix Inequality Approaches to Koopman Operator Approximation
• Consistency of trace norm minimization
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• A performance analysis framework for SOCP algorithms in noisy compressed sensing
• Information Theoretic Bounds for Low-Rank Matrix Completion
• Learning from Comparisons and Choices
• Nuclear Norm based Matrix Regression with Applications to Face Recognition with Occlusion and Illumination Changes
• Millimeter Wave Channel Estimation via Exploiting Joint Sparse and Low-Rank Structures
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Finding a low-rank basis in a matrix subspace
• A sequential constraint relaxation framework to design phase-coded sequences for radar systems
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
• Provable Low Rank Phase Retrieval
• Efficient Optimization Algorithms for Robust Principal Component Analysis and Its Variants
• A Parallelizable Acceleration Framework for Packing Linear Programs
• A Greedy Algorithm for Matrix Recovery with Subspace Prior Information
• Latent Variable Modeling with Diversity-Inducing Mutual Angular Regularization
• Tensor Decomposition for Signal Processing and Machine Learning
• Atomic Norm Denoising With Applications to Line Spectral Estimation
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Leveraging Diversity and Sparsity in Blind Deconvolution
• Learning Parameters for Weighted Matrix Completion via Empirical Estimation
• Approximation Theory of Matrix Rank Minimization and Its Application to Quadratic Equations
• A New Nonconvex Strategy to Affine Matrix Rank Minimization Problem
• Balanced Augmented Lagrangian Method for Convex Programming
• RIP-based performance guarantee for low-tubal-rank tensor recovery
• Optimal Regularization Under Uncertainty: Distributional Robustness and Convexity Constraints
• On the computational and statistical complexity of over-parameterized matrix sensing
• High-dimensional covariance matrix estimation using a low-rank and diagonal decomposition
• Two-Layer Linear Auto-Regressive Models Estimate Latent States
• Optimal RIP bounds for sparse signals recovery via ℓ minimization
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Low-rank optimization with trace norm penalty
• Similarity Learning via Adaptive Regression and Its Application to Image Retrieval
• Low-Rank High-Order Tensor Completion With Applications in Visual Data
• LMI Properties and Applications in Systems, Stability, and Control Theory
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Deep learned SVT: Unrolling singular value thresholding to obtain better MSE
• Tensor Restricted Isometry Property Analysis For a Large Class of Random Measurement Ensembles
• An equivalence between critical points for rank constraints versus low-rank factorizations
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Convex Tensor Decomposition via Structured Schatten Norm Regularization
• Various thresholds for ℓ₁-optimization in compressed sensing
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Differentially Private Multi-party Computation: Optimality of Non-Interactive Randomized Response
• Proximal Hamiltonian Monte Carlo
• Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Binno: A 1st-order method for Bi-level Nonconvex Nonsmooth Optimization for Matrix Factorizations
• Leveraging semantic similarity for experimentation with AI-generated treatments
• Exact Sparse Orthogonal Dictionary Learning
• Vandermonde Decomposition of Multilevel Toeplitz Matrices with Application to Multidimensional Super-Resolution
• Locally upper Lipschitz of the perturbed KKT system of Ky Fan k-norm matrix conic optimization problems
• Performance Analysis of Convex LRMR based Passive SAR Imaging
• Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Simplifying Optimal Transport through Schatten-p Regularization
• Clipped Matrix Completion: A Remedy for Ceiling Effects
• Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent Algorithm
• Selective Factor Extraction in High Dimensions
• Sparse Phase Retrieval: Convex Algorithms and Limitations
• On Error Bounds for Rank-Constrained Affine Matrix Sets
• Universality in Learning from Linear Measurements
• Implicit Regularization in Deep Matrix Factorization
• Semidefinite Programming and Nash Equilibria in Bimatrix Games
• A Probabilistic Basis for Low-Rank Matrix Learning
• On the Benefits of Weight Normalization for Overparameterized Matrix Sensing
• Bilinear Bandits with Low-rank Structure
• On the Performance of Amplitude-Based Models for Low-Rank Matrix Recovery
• Non-linear Dimensionality Regularizer for Solving Inverse Problems
• Bundle methods for dual atomic pursuit
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Efficient iterative thresholding algorithms with functional feedbacks and convergence analysis
• Learning Data-adaptive Nonparametric Kernels
• A Recovery Theory for Diffusion Priors: Deterministic Analysis of the Implicit Prior Algorithm
• Improved Algorithms for Matrix Recovery from Rank-One Projections
• Learning Tensors in Reproducing Kernel Hilbert Spaces with Multilinear Spectral Penalties
• An algorithm for online tensor prediction
• A General Decision Theory for Huber's ε-Contamination Model
• Block-Matching Convolutional Neural Network for Image Denoising
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Fixed-Rank Representation for Unsupervised Visual Learning
• Convex Optimization without Projection Steps
• A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
• Living on the edge: Phase transitions in convex programs with random data
• Quantum State Tomography for Tensor Networks in Two Dimensions
• Scalable Hessian-free Proximal Conjugate Gradient Method for Nonconvex and Nonsmooth Optimization
• One-step Multi-view Clustering With Adaptive Low-rank Anchor-graph Learning
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Subspace Change-Point Detection via Low-Rank Matrix Factorisation
• Top-N Recommendation with Novel Rank Approximation
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Convex relaxations of structured matrix factorizations
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• IHT dies hard: Provable accelerated Iterative Hard Thresholding
• A Block Lanczos with Warm Start Technique for Accelerating Nuclear Norm Minimization Algorithms
• Low rank matrix recovery from Clifford orbits
• Image Segmentation Using Subspace Representation and Sparse Decomposition
• Frequency Response Identification of Low-Order Systems: Finite-Sample Analysis
• What Fundamental Structure in Reward Functions Enables Efficient Sparse-Reward Learning?
• An Overview of Lead and Accompaniment Separation in Music
• Guaranteed Rank Minimization via Singular Value Projection
• Regularization for Design
• ER-LoRA: Effective-Rank Guided Adaptation for Weather-Generalized Depth Estimation
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
• Convex optimization for the planted k-disjoint-clique problem
• Extreme MRI: Large-Scale Volumetric Dynamic Imaging from Continuous Non-Gated Acquisitions
• Efficient Rank Minimization via Solving Non-convexPenalties by Iterative Shrinkage-Thresholding Algorithm
• From Blind deconvolution to Blind Super-Resolution through convex programming
• Numerical Optimization for Tensor Disentanglement
• Implicit Regularization in Tensor Factorization
• A Sequential Subspace Method for Millimeter Wave MIMO Channel Estimation
• Sharp oracle inequalities for the prediction of a high-dimensional matrix
• Upper Bounds on the Error of Sparse Vector and Low-Rank Matrix Recovery
• AIC, Cp and estimators of loss for elliptically symmetric distributions
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• Efficient Online Minimization for Low-Rank Subspace Clustering
• A Splitting Augmented Lagrangian Method for Low Multilinear-Rank Tensor Recovery
• Low-rank matrix recovery via rank one tight frame measurements
• Generalized low rank approximation to the symmetric positive semidefinite matrix
• Convex Optimization Methods for Dimension Reduction and Coefficient Estimation in Multivariate Linear Regression
• Fine-grained Classification using Heterogeneous Web Data and Auxiliary Categories
• Matrix Completion with Prior Subspace Information via Maximizing Correlation
• Efficient Reward Identification In Max Entropy Reinforcement Learning with Sparsity and Rank Priors
• A Trace-restricted Kronecker-Factored Approximation to Natural Gradient
• Clustering a Mixture of Gaussians with Unknown Covariance
• Reconstruction of signals from their autocorrelation and cross-correlation vectors, with applications to phase retrieval and blind channel estimation
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Let's Measure Information Step-by-Step: LLM-Based Evaluation Beyond Vibes
• Matrix Factorization-Based Solar Spectral Irradiance Missing Data Imputation with Uncertainty Quantification
• Goodness-of-fit tests on manifolds
• The Minimum-Rank Gram Matrix Completion via Modified Fixed Point Continuation Method
• Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction
• Robust Ordinal Embedding from Contaminated Relative Comparisons
• Quantum Tomography by Regularized Linear Regression
• Accelerated and Inexact Soft-Impute for Large-Scale Matrix and Tensor Completion
• Blind Image Denoising via Dependent Dirichlet Process Tree
• Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence
• On convexification/optimization of functionals including an l2-misfit term
• SOS Tensor Decomposition: Theory and Applications
• Multi-label Learning with Missing Labels using Mixed Dependency Graphs
• Robust Sparse Reduced Rank Regression in High Dimensions
• Low-rank Matrix Completion in a General Non-orthogonal Basis
• An inexact alternating projection method with application to matrix completion
• Multi-Dimensional Wireless Tomography with Tensor-Based Compressed Sensing
• The minimal measurement number for low-rank matrices recovery
• Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm
• Fast and Provable Algorithms for Spectrally Sparse Signal Reconstruction via Low-Rank Hankel Matrix Completion
• Structured low-rank matrix completion for forecasting in time series\n analysis
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Confidence-Constrained Maximum Entropy Framework for Learning from Multi-Instance Data
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Leave-one-out Approach for Matrix Completion: Primal and Dual Analysis
• Revisiting L21-norm Robustness with Vector Outlier Regularization
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Convergence bounds for nonlinear least squares and applications to tensor recovery
• Low Tensor Train- and Low Multilinear Rank Approximations for De-speckling and Compression of 3D Optical Coherence Tomography Images
• Estimating Traffic and Anomaly Maps via Network Tomography
• Online Forecasting Matrix Factorization
• Solving Systems of Quadratic Equations via Exponential-type Gradient Descent Algorithm
• Multi-sample Estimation of Bacterial Composition Matrix in Metagenomics Data
• Optimal Sample Complexity for Stable Matrix Recovery
• Stochastic continuum armed bandit problem of few linear parameters in high dimensions
• On the construction of general cubature formula by flat extensions
• Efficient MCMC Sampling for Bayesian Matrix Factorization by Breaking Posterior Symmetries
• Sharp Oracle Inequalities for Low-complexity Priors
• Performance analysis of weighted low rank model with sparse image histograms for face recognition under lowlevel illumination and occlusion
• A Fast Algorithm for Convolutional Structured Low-Rank Matrix Recovery
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Tensor-Tensor Products, Group Representations, and Semidefinite Programming
• Synthesizing Invariant Barrier Certificates via Difference-of-Convex Programming
• A Review of Speaker Diarization: Recent Advances with Deep Learning
• Smooth tensor decomposition with application to ambulatory blood pressure monitoring data
• Optimal spectral norm rates for noisy low-rank matrix completion
• Provably convergent acceleration in factored gradient descent with applications in matrix sensing
• Exact Joint Sparse Frequency Recovery via Optimization Methods
• Adaptive iterative singular value thresholding algorithm to low-rank matrix recovery
• Machine Learning for Spatiotemporal Sequence Forecasting: A Survey
• Regularizers versus Losses for Nonlinear Dimensionality Reduction: A Factored View with New Convex Relaxations
• Efficient tensor completion: Low-rank tensor train
• Kernel based low-rank sparse model for single image super-resolution
• Infrared target tracking based on proximal robust principal component analysis method
• Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximation
• Learning Non-Parametric Basis Independent Models from Point Queries via\n Low-Rank Methods
• Estimation of low-rank tensors via convex optimization
• Unified Scalable Equivalent Formulations for Schatten Quasi-Norms
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
• Bayesian Tensorized Neural Networks with Automatic Rank Selection
• Exploiting Cognition in ISAR Processing for Spectral Compatibility Applications
• The perturbation analysis of nonconvex low-rank matrix robust recovery
• Asymptotic Log-Det Rank Minimization via (Alternating) Iteratively Reweighted Least Squares
• Discrete-Aware Matrix Completion via Proximal Gradient
• Improved Algorithms for White-Box Adversarial Streams
• The Nonconvex Geometry of Linear Inverse Problems
• Linear convergence of the Randomized Sparse Kaczmarz Method
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• OAAE: Adversarial Autoencoders for Novelty Detection in Multi-modal Normality Case via Orthogonalized Latent Space
• Nonparametric Trace Regression in High Dimensions via Sign Series Representation
• On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
• Convex Formulation for Planted Quasi-Clique Recovery
• Illumination strategies for intensity-only imaging
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle
• Sharp recovery bounds for convex demixing, with applications
• Fast Optimization Algorithm on Riemannian Manifolds and Its Application in Low-Rank Representation
• Sparse Subspace Clustering: Algorithm, Theory, and Applications
• Low Rank Forecasting
• Riemannian Conjugate Gradient Descent Method for Third-Order Tensor Completion
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• SPRITE: A Response Model For Multiple Choice Testing
• Sparse recovery via nonconvex regularized M-estimators over ℓ_q-balls
• The Landscape of Non-convex Empirical Risk with Degenerate Population Risk
• How well can we learn large factor models without assuming strong factors?
• Matrix Factorization Method for Decentralized Recommender Systems
• Robust Tensor Completion via Gradient Tensor Nulclear L1-L2 Norm for Traffic Data Recovery
• Blind Deconvolution using Convex Programming
• High-dimensional Time Series Prediction with Missing Values
• A Non-monotone Alternating Updating Method for A Class of Matrix Factorization Problems
• Sharp MSE Bounds for Proximal Denoising
• Rank Restricted Semidefinite Matrices and Image Closedness
• Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization
• Checking the strict positivity of Kraus maps is NP-hard
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Empirical Chaos Processes and Blind Deconvolution
• Every critical point of an L0 composite minimization problem is a local minimizer
• kFW: A Frank-Wolfe style algorithm with stronger subproblem oracles
• Joint Space Decomposition-and-Synthesis Theory for K-User MIMO Channels: Interference Alignment and DoF Region
• A Scalable Factorization Approach for High-Order Structured Tensor Recovery
• Implicit Regularization in Matrix Sensing via Mirror Descent
• The local convexity of solving systems of quadratic equations
• Regularization methods for learning incomplete matrices
• Policy Search with High-Dimensional Context Variables
• Optimistic lower bounds for convex regularized least-squares
• Matrix Completion with Quantified Uncertainty through Low Rank Gaussian Copula
• PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations
• Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformers
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-Rank Matrix Optimization
• Convex Latent Effect Logit Model via Sparse and Low-rank Decomposition
• A Saddle Point Algorithm for Robust Data-Driven Factor Model Problems
• Low-rank Matrix Completion using Alternating Minimization
• Capacity Region of MISO Broadcast Channel for Simultaneous Wireless Information and Power Transfer
• A Nonconvex Nonsmooth Regularization Method for Compressed Sensing and Low-Rank Matrix Completion
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• A Parallel Best-Response Algorithm with Exact Line Search for Nonconvex Sparsity-Regularized Rank Minimization
• Semidefinite Programming For Chance Constrained Optimization Over Semialgebraic Sets
• Compressed sensing of block-sparse positive vectors
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Sum-of-square-of-rational-function based representations of positive semidefinite polynomial matrices
• Efficient Neural Interaction Function Search for Collaborative Filtering
• Regression on fixed-rank positive semidefinite matrices: a Riemannian approach
• Affine matrix rank minimization problem via non-convex fraction function penalty
• Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion
• How Much Restricted Isometry is Needed In Nonconvex Matrix Recovery?
• Block-length dependent thresholds in block-sparse compressed sensing
• Index Coding and Network Coding via Rank Minimization
• TFPnP: Tuning-free Plug-and-Play Proximal Algorithm with Applications to Inverse Imaging Problems
• Missing Value Imputation for Mixed Data via Gaussian Copula
• Alternating Energy Minimization Methods for Multi-term Matrix Equations
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-rank Matrices
• Identifiability Conditions for Multi-channel Blind Deconvolution with Short Filters
• Recovering Multiple Nonnegative Time Series From a Few Temporal Aggregates
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Robust Low-Rank Subspace Segmentation with Semidefinite Guarantees
• Low-Rank Autoregressive Tensor Completion for Multivariate Time Series Forecasting
• Efficient Structured Matrix Rank Minimization
• Nonparametric Reduced Rank Regression
• Enhancing low-rank solutions in semidefinite relaxations of Boolean quadratic problems
• Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima
• A framework to characterize performance of LASSO algorithms
• Beyond Low-Rank Representations: Orthogonal Clustering Basis Reconstruction with Optimized Graph Structure for Multi-view Spectral Clustering
• Enhanced image approximation using shifted rank-1 reconstruction
• Identifiability through special linear measurements
• A Convex Approach to Frisch-Kalman Problem
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• One Rank at a Time: Cascading Error Dynamics in Sequential Learning
• Multifrequency interferometric imaging with intensity-only measurements
• Multi-Tensor Network Representation for High-Order Tensor Completion
• Sample Complexity of Power System State Estimation using Matrix Completion
• Scalable and adaptive prediction bands with kernel sum-of-squares
• Learning Low-Complexity Autoregressive Models via Proximal Alternating Minimization
• General Low-rank Matrix Optimization: Geometric Analysis and Sharper Bounds
• Alternating Strategies Are Good For Low-Rank Matrix Reconstruction
• Learning Robust Low-Rank Representations
• Solving ptychography with a convex relaxation
• A Comparison of Clustering and Missing Data Methods for Health Sciences
• Pursuits in Structured Non-Convex Matrix Factorizations
• Distributable Consistent Multi-Object Matching
• A Sparsity Inducing Nuclear-Norm Estimator (SpINNEr) for Matrix-Variate Regression in Brain Connectivity Analysis
• The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks
• Approximating the Trace Distance Between Product Quantum States
• On the Consistency of Compressed Modes for Variational Problems
• Minimum n-Rank Approximation via Iterative Hard Thresholding
• A Super-Resolution Framework for Tensor Decomposition
• New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Low-Rank Modeling and Its Applications in Image Analysis
• Dropping Convexity for Faster Semi-definite Optimization
• A Convergent Semi-Proximal Alternating Direction Method of Multipliers for Recovering Internet Traffics from Link Measurements
• Relax, no need to round: integrality of clustering formulations
• Output behavior equivalence and simultaneous subspace identification of systems and faults
• AltLoRA: Towards Better Gradient Approximation in Low-Rank Adaptation with Alternating Projections
• Underwater moving target detection using online robust principal component analysis and multimodal anomaly detection
• Learning Mixtures of Gaussians in High Dimensions
• Distributed Localization of Tree-structured Scattered Sensor Networks
• Cyclic-Shift Sparse Kronecker Tensor Classifier for Signal-Region Detection in Neuroimaging
• Inference for Heterogeneous Effects using Low-Rank Estimation of Factor Slopes
• Balancing Accuracy and Diversity in Recommendations using Matrix Completion Framework
• Channel Vector Subspace Estimation from Low-Dimensional Projections
• Consistent Collective Matrix Completion under Joint Low Rank Structure
• Tensor Completion for Estimating Missing Values in Visual Data
• Improving Power Systems Controllability via Edge Centrality Measures
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Low-Rank and Total Variation Regularization and Its Application to Image Recovery
• Local Linear Convergence of Forward-Backward under Partial Smoothness
• Clustering-Based Low-Rank Matrix Approximation for Medical Image Compression
• Non-Negative Matrix Factorization, Convexity and Isometry
• On Convex Duality in Linear Inverse Problems
• Factorization Approach for Low-complexity Matrix Completion Problems:\n Exponential Number of Spurious Solutions and Failure of Gradient Methods
• Decentralized Dictionary Learning Over Time-Varying Digraphs
• Structured Matrix Recovery via the Generalized Dantzig Selector
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Multiplicative Noise Removal: Nonlocal Low-Rank Model and Its Proximal Alternating Reweighted Minimization Algorithm
• Bridging and Improving Theoretical and Computational Electric Impedance Tomography via Data Completion
• Alternating Iteratively Reweighted Minimization Algorithms for Low-Rank Matrix Factorization
• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
• Quantitative Chemical Exchange Saturation Transfer Imaging with Golden-Angle Radial k-Space and Locally Low-Rank Reconstruction
• GFB-MRF: A parallel spatial and Bloch manifold regularized iterative reconstruction method for MR Fingerprinting
• Tensor Completion Algorithms in Big Data Analytics
• A new graph parameter related to bounded rank positive semidefinite matrix completions
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix\n Recovery
• Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms
• Tensor-Ring Nuclear Norm Minimization and Application for Visual Data Completion
• Complexity Aspects of Fundamental Questions in Polynomial Optimization
• Burer-Monteiro factorizability of nuclear norm regularized optimization
• Beyond Quadratic Costs in LQR: Bregman Divergence Control
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems
• Optimal tracking for pairs of qubit states
• Polar Alignment and Atomic Decomposition
• Multiview Spectral Clustering via Structured Low-Rank Matrix Factorization
• Equivalence and Strong Equivalence between Sparsest and Least ℓ₁-Norm Nonnegative Solutions of Linear Systems and Their Application
• Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators
• Sparse Functional Identification of Complex Cells from Spike Times and the Decoding of Visual Stimuli
• Efficient and Guaranteed Rank Minimization by Atomic Decomposition
• Phase diagram of matrix compressed sensing
• Online Optimization for Large-Scale Max-Norm Regularization
• On identity testing of tensors, low-rank recovery and compressed sensing
• Quaternion Nuclear Norms Over Frobenius Norms Minimization for Robust Matrix Completion
• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent
• Low-Rank Adaptation Redux for Large Models
• Nonconvex Linear System Identification with Minimal State Representation
• Vandermonde Decomposition of Multilevel Toeplitz Matrices With Application to Multidimensional Super-Resolution
• An Analysis of Dropout for Matrix Factorization
• Stability of low-rank matrix recovery and its connections to Banach space geometry
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Multiple Images Recovery Using a Single Affine Transformation
• High-dimensional estimation with geometric constraints
• On Universal Features for High-Dimensional Learning and Inference
• Generalized singular value thresholding operator to affine matrix rank minimization problem
• Stealthy Sensor Attacks Against Direct Data-Driven Controllers
• Maximally genuine multipartite entangled mixed X-states ofN-qubits
• Fundamental Performance Limits for Ideal Decoders in High-Dimensional Linear Inverse Problems
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Positive Semidefinite Matrix Factorization: A Connection With Phase Retrieval and Affine Rank Minimization
• Beamforming Tradeoffs for Initial UE Discovery in Millimeter-Wave MIMO Systems
• Matrix completion based on Gaussian parameterized belief propagation
• On the Convergence of Projected-Gradient Methods with Low-Rank Projections for Smooth Convex Minimization over Trace-Norm Balls and Related Problems
• Lower and Upper Bounds on the VC-Dimension of Tensor Network Models
• Compressive Sensing of Sparse Tensors
• An alternating direction algorithm for matrix completion with nonnegative factors
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Low-rank Approximation of Linear Maps
• Trace Norm Regularised Deep Multi-Task Learning
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Transfer Learning for High-dimensional Reduced Rank Time Series Models
• Generalized Separable Nonnegative Matrix Factorization
• Sparse Array Beamforming Design for Wideband Signal Models
• Stable pure state quantum tomography from five orthonormal bases
• Symmetric Bilinear Regression for Signal Subgraph Estimation
• Stable Manifold Embeddings with Structured Random Matrices
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Randomized Robust Subspace Recovery and Outlier Detection for High Dimensional Data Matrices
• Subspace Expanders and Matrix Rank Minimization
• Accelerated Linearized Bregman Method
• Compressed-sensing tomography for qudits in Hilbert spaces of non-power-of-two dimensions
• Interpreting latent variables in factor models via convex optimization
• Learning with tree tensor networks: complexity estimates and model selection
• Compressed Sensing off the Grid
• Exact Multistatic Interferometric Imaging via Generalized Wirtinger Flow
• Optimal Precoders for Tracking the AoD and AoA of a mmWave Path
• Experimental Study of Optimal Measurements for Quantum State Tomography
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
• On Recoverability of Randomly Compressed Tensors With Low CP Rank
• From Sparse Signals to Sparse Residuals for Robust Sensing

Related

• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
• Exploring Algorithmic Limits of Matrix Rank Minimization under Affine Constraints
• Efficient and Guaranteed Rank Minimization by Atomic Decomposition
• A New Nonconvex Strategy to Affine Matrix Rank Minimization Problem
• Convergence of fixed-point continuation algorithms for matrix rank minimization