Timezone: »
Based on a new atomic norm, we propose a new convex formulation for sparse matrix factorization problems in which the number of nonzero elements of the factors is assumed fixed and known. The formulation counts sparse PCA with multiple factors, subspace clustering and low-rank sparse bilinear regression as potential applications. We compute slow rates and an upper bound on the statistical dimension of the suggested norm for rank 1 matrices, showing that its statistical dimension is an order of magnitude smaller than the usual l_1-norm, trace norm and their combinations. Even though our convex formulation is in theory hard and does not lead to provably polynomial time algorithmic schemes, we propose an active set algorithm leveraging the structure of the convex problem to solve it and show promising numerical results.
Author Information
Emile Richard (Amazon)
Guillaume R Obozinski (Ecole des Ponts - ParisTech)
Jean-Philippe Vert (Owkin / PSL University)
More from the Same Authors
-
2021 Poster: Framing RNN as a kernel method: A neural ODE approach »
Adeline Fermanian · Pierre Marion · Jean-Philippe Vert · Gérard Biau -
2021 Poster: Reverse-Complement Equivariant Networks for DNA Sequences »
Vincent Mallet · Jean-Philippe Vert -
2021 Oral: Framing RNN as a kernel method: A neural ODE approach »
Adeline Fermanian · Pierre Marion · Jean-Philippe Vert · Gérard Biau -
2018 Poster: Relating Leverage Scores and Density using Regularized Christoffel Functions »
Edouard Pauwels · Francis Bach · Jean-Philippe Vert -
2015 : Learning from Rankings »
Jean-Philippe Vert -
2015 Poster: Recognizing retinal ganglion cells in the dark »
Emile Richard · Georges A Goetz · E.J. Chichilnisky -
2014 Poster: A statistical model for tensor PCA »
Emile Richard · Andrea Montanari -
2014 Poster: Cone-Constrained Principal Component Analysis »
Yash Deshpande · Andrea Montanari · Emile Richard -
2013 Workshop: Machine Learning in Computational Biology »
Jean-Philippe Vert · Anna Goldenberg · Sara Mostafavi · Oliver Stegle -
2012 Workshop: Machine Learning in Computational Biology »
Jean-Philippe Vert · Anna Goldenberg · Christina Leslie -
2012 Poster: Link Prediction in Graphs with Autoregressive Features »
Emile Richard · Stephane Gaiffas · Nicolas Vayatis -
2012 Session: Oral Session 9 »
Jean-Philippe Vert -
2012 Poster: A latent factor model for highly multi-relational data »
Rodolphe Jenatton · Nicolas Le Roux · Antoine Bordes · Guillaume R Obozinski -
2011 Workshop: Machine Learning in Computational Biology »
Jean-Philippe Vert · Gunnar Rätsch · Yanjun Qi · Tomer Hertz · Anna Goldenberg · Christina Leslie -
2011 Workshop: Sparse Representation and Low-rank Approximation »
Ameet S Talwalkar · Lester W Mackey · Mehryar Mohri · Michael W Mahoney · Francis Bach · Mike Davies · Remi Gribonval · Guillaume R Obozinski -
2011 Poster: Trace Lasso: a trace norm regularization for correlated designs »
Edouard Grave · Guillaume R Obozinski · Francis Bach -
2010 Workshop: Machine Learning in Computational Biology »
Gunnar Rätsch · Jean-Philippe Vert · Tomer Hertz · Yanjun Qi -
2010 Poster: Link Discovery using Graph Feature Tracking »
Emile Richard · Nicolas Baskiotis · Theos Evgeniou · Nicolas Vayatis -
2010 Poster: Network Flow Algorithms for Structured Sparsity »
Julien Mairal · Rodolphe Jenatton · Guillaume R Obozinski · Francis Bach -
2010 Poster: Fast detection of multiple change-points shared by many signals using group LARS »
Jean-Philippe Vert · Kevin Bleakley -
2009 Workshop: Temporal Segmentation: Perspectives from Statistics, Machine Learning, and Signal Processing »
Stephane Canu · Olivier Cappé · Arthur Gretton · Zaid Harchaoui · Alain Rakotomamonjy · Jean-Philippe Vert -
2009 Workshop: Machine Learning in Computational Biology »
Gal Chechik · Tomer Hertz · William S Noble · Yanjun Qi · Jean-Philippe Vert · Alexander Zien -
2009 Mini Symposium: Machine Learning in Computational Biology »
Yanjun Qi · Jean-Philippe Vert · Gal Chechik · Alexander Zien · Tomer Hertz · William S Noble -
2009 Poster: White Functionals for Anomaly Detection in Dynamical Systems »
Marco Cuturi · Jean-Philippe Vert · Alexandre d'Aspremont -
2008 Poster: Clustered Multi-Task Learning: A Convex Formulation »
Laurent Jacob · Francis Bach · Jean-Philippe Vert -
2008 Poster: High-dimensional union support recovery in multivariate regression »
Guillaume R Obozinski · Martin J Wainwright · Michael Jordan -
2008 Spotlight: High-dimensional union support recovery in multivariate regression »
Guillaume R Obozinski · Martin J Wainwright · Michael Jordan -
2008 Spotlight: Clustered Multi-Task Learning: A Convex Formulation »
Laurent Jacob · Francis Bach · Jean-Philippe Vert