Sparse inference using approximate message passing | Michael Riis Andersen
| | Abstract | This thesis deals with probabilistic methods for finding sparse solutions to illposed linear inverse problems using both the single measurement vector (SMV) formulation and multiple measurement vector (MMV) formulation. Specifically, this thesis investigates the novel algorithm called approximate message passing (AMP) and its Bayesian generalization called generalized approximate message passing (GAMP). The AMP algorithm was initially proposed by Donoho et al. (2009) to solve the linear inverse problem in the context of compressed sensing and later generalized by Rangan (2010). Both algorithms are based on approximations of sum-product algorithm formulated for factors graphs. Through numerical simulations, it is verified that the AMP algorithms are able to achieve superior performance in terms of the sparsity under-sampling trade-off for the basis pursuit problem, while maintaining a low computational complexity. Moreover, the GAMP framework is combined with the sparsity promoting spike and slap prior to derive an inference algorithm for the inverse problem in the SMV formulation. This algorithm is extended to the MMV formulation, which allows the use of multiple measurement vectors by imposing a common sparsity pattern on the measurement vectors. This method, which is coined AMP-MMV, provides soft estimates of both the solution and the underlying support. A thorough numerical study verifies the benefits of the MMV formulation and compares it to state-of-the-art methods. This comparison shows that the AMP-MMV is able to match the recovery capabilities of these methods, while maintaining a computational complexity that is linear in all problem dimensions. Yet another model is considered, the AMP-DCS model, which relaxes the assumption of the common sparsity pattern by assuming the sparsity pattern is slowly changing over time according to a binary Markov chain. By means of numerical experiments, it is demonstrated that this approach is preferable to the SMV approach. For automatic tuning of the hyperparameters, Expectation-Maximization (EM) algorithms are derived for both the SMV and MMV formulation. | | Type | Master's thesis [Academic thesis] | | Year | 2014 | | Publisher | Technical University of Denmark, Department of Applied Mathematics and Computer Science | | Address | Matematiktorvet, Building 303B, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk | | Series | DTU Compute M.Sc.-2014 | | Note | DTU Supervisor: Lars Kai Hansen, lkai@dtu.dk, DTU Compute | | Electronic version(s) | [pdf] | | Publication link | http://www.compute.dtu.dk/English.aspx | | BibTeX data | [bibtex] | | IMM Group(s) | Intelligent Signal Processing |
|