Skip to Main content Skip to Navigation

Convex matrix sparsity for demixing with an application to graphical model structure estimation

Abstract : The goal of machine learning is to learn a model from some data that will make accurate predictions on data that it has not seen before. In order to obtain a model that will generalize on new data, and avoid overfitting, we need to restrain the model. These restrictions are usually some a priori knowledge of the structure of the model. First considered approaches included a regularization, first ridge regression and later Lasso regularization for inducing sparsity in the solution. Sparsity, also known as parsimony, has emerged as a fundamental concept in machine learning. Parsimonious models are appealing since they provide more interpretability and better generalization (avoid overfitting) through the reduced number of parameters. Beyond general sparsity and in many cases, models are constrained structurally so they have a simple representation in terms of some fundamental elements, consisting for example of a collection of specific vectors, matrices or tensors. These fundamental elements are called atoms. In this context, atomic norms provide a general framework for estimating these sorts of models. The goal of this thesis is to use the framework of convex sparsity provided by atomic norms to study a form of matrix sparsity. First, we develop an efficient algorithm based on Frank-Wolfe methods that is particularly adapted to solve problems with an atomic norm regularization. Then, we focus on the structure estimation of Gaussian graphical models, where the structure of the graph is encoded in the precision matrix and study the case with unobserved variables. We propose a convex formulation with an algorithmic approach and provide a theoretical result that states necessary conditions for recovering the desired structure. Finally, we consider the problem of signal demixing into two or more components via the minimization of a sum of norms or gauges, encoding each a structural prior on the corresponding components to recover. In particular, we provide general exact recovery guarantees in the noiseless setting based on incoherence measures
Document type :
Complete list of metadata

Cited literature [156 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Friday, April 26, 2019 - 3:03:07 PM
Last modification on : Saturday, January 15, 2022 - 3:58:28 AM


Version validated by the jury (STAR)


  • HAL Id : tel-02112207, version 1



Marina Vinyes. Convex matrix sparsity for demixing with an application to graphical model structure estimation. Signal and Image Processing. Université Paris-Est, 2018. English. ⟨NNT : 2018PESC1130⟩. ⟨tel-02112207⟩



Record views


Files downloads