Convex Sparse Matrix Factorizations

Abstract

We present a convex formulation of dictionary learning for sparse signal decomposition. Convexity is obtained by replacing the usual explicit upper bound on the dictionary size by a convex rank-reducing term similar to the trace norm. In particular, our formulation introduces an explicit trade-off between size and sparsity of the decomposition of rectangular matrices. Using a large set of synthetic examples, we compare the estimation abilities of the convex and non-convex approaches, showing that while the convex formulation has a single local minimum, this may lead in some cases to performance which is inferior to the local minima of the non-convex formulation.

References in corpus (11)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Consistency of trace norm minimization

Cited by in corpus (30)

• Structured Sparse Principal Component Analysis
• Exact Recovery of Sparsely-Used Dictionaries
• Global Optimality in Tensor Factorization, Deep Learning, and Beyond
• Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training
• On Universal Features for High-Dimensional Learning and Inference
• Local stability and robustness of sparse dictionary learning in the presence of noise
• Convex relaxations of structured matrix factorizations
• Tight convex relaxations for sparse matrix factorization
• Stochastic Variance Reduction Methods for Saddle-Point Problems
• Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
• A Sparse SVD Method for High-dimensional Data
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• 1-Bit Matrix Completion under Exact Low-Rank Constraint
• Generalized Conditional Gradient for Sparse Estimation
• Matrix factorization with Binary Components
• A Stochastic Proximal Point Algorithm for Saddle-Point Problems
• Online Learning for Matrix Factorization and Sparse Coding
• Matrix Completion and Related Problems via Strong Duality
• Convex Factorization Machine for Regression
• An $O(s^r)$-Resolution ODE Framework for Understanding Discrete-Time Algorithms and Applications to the Linear Convergence of Minimax Problems
• Sparse and spurious: dictionary learning with noise and outliers
• An Analysis of Dropout for Matrix Factorization
• Online Convex Matrix Factorization with Representative Regions
• Method with Batching for Stochastic Finite-Sum Variational Inequalities in Non-Euclidean Setting
• Robust Generalization of Quadratic Neural Networks via Function Identification
• The Nonconvex Geometry of Linear Inverse Problems
• On the Minimax Risk of Dictionary Learning
• Optimal Analysis of Method with Batching for Monotone Stochastic Finite-Sum Variational Inequalities
• Pursuits in Structured Non-Convex Matrix Factorizations
• Online Optimization for Large-Scale Max-Norm Regularization