Reconstruction of jointly sparse vectors via manifold optimization

Armenak Petrosyan; Hoang Tran; Clayton Webster

doi:10.1016/j.apnum.2019.05.022

Reconstruction of jointly sparse vectors via manifold optimization

Armenak Petrosyan, Hoang Tran, Clayton Webster

Multiscale Methods

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

In this paper, we consider the challenge of reconstructing jointly sparse vectors from linear measurements. Firstly, we show that by utilizing the rank of the output data matrix we can reduce the problem to a full column rank case. This result reveals a reduction in the computational complexity of the original problem and enables a simple implementation of joint sparse recovery algorithms for full-rank setting. Secondly, we propose a new method for joint sparse recovery in the form of a non-convex optimization problem on a non-compact Stiefel manifold. In our numerical experiments our method outperforms the commonly used ℓ_2,1 minimization in the sense that much fewer measurements are required for accurate sparse reconstructions. We postulate this approach possesses the desirable rank aware property, that is, being able to take advantage of the rank of the unknown matrix to improve the recovery.

Original language	English
Pages (from-to)	140-150
Number of pages	11
Journal	Applied Numerical Mathematics
Volume	144
DOIs	https://doi.org/10.1016/j.apnum.2019.05.022
State	Published - Oct 2019

Funding

This work is supported by the National Science Foundation , Division of Mathematical Sciences, Computational Mathematics program under contract number DMS1620280 ; the U.S. Department of Energy , Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under contract number ERKJ314 ; Scientific Discovery through Advanced Computing (SciDAC) program through the FASTMath Institute under Contract No. DE-AC02-05CH11231 ; and, the Laboratory Directed Research and Development program at the Oak Ridge National Laboratory , which is operated by UT-Battelle, LLC., for the U.S. Department of Energy under Contract DE-AC05-00OR22725 . We want to thank Richard Barnard (Western Washington University) for suggesting the use of Huber regularization and Carola-Bibiane Schönlieb (University of Cambridge) for pointing out the Γ-convergence argument for Huber regularization to us. We also thank the anonymous referee for valuable suggestions. This work is supported by the National Science Foundation, Division of Mathematical Sciences, Computational Mathematics program under contract number DMS1620280; the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under contract number ERKJ314; Scientific Discovery through Advanced Computing (SciDAC) program through the FASTMath Institute under Contract No. DE-AC02-05CH11231; and, the Laboratory Directed Research and Development program at the Oak Ridge National Laboratory, which is operated by UT-Battelle, LLC. for the U.S. Department of Energy under Contract DE-AC05-00OR22725.

Keywords

Huber regularization
Joint sparsity
Manifold optimization
Non-compact Stiefel manifold
Non-convex optimization

Access to Document

10.1016/j.apnum.2019.05.022

Cite this

@article{ad859602f57843c79246da3dca58cdf8,

title = "Reconstruction of jointly sparse vectors via manifold optimization",

abstract = "In this paper, we consider the challenge of reconstructing jointly sparse vectors from linear measurements. Firstly, we show that by utilizing the rank of the output data matrix we can reduce the problem to a full column rank case. This result reveals a reduction in the computational complexity of the original problem and enables a simple implementation of joint sparse recovery algorithms for full-rank setting. Secondly, we propose a new method for joint sparse recovery in the form of a non-convex optimization problem on a non-compact Stiefel manifold. In our numerical experiments our method outperforms the commonly used ℓ2,1 minimization in the sense that much fewer measurements are required for accurate sparse reconstructions. We postulate this approach possesses the desirable rank aware property, that is, being able to take advantage of the rank of the unknown matrix to improve the recovery.",

keywords = "Huber regularization, Joint sparsity, Manifold optimization, Non-compact Stiefel manifold, Non-convex optimization",

author = "Armenak Petrosyan and Hoang Tran and Clayton Webster",

note = "Publisher Copyright: {\textcopyright} 2019 IMACS",

year = "2019",

month = oct,

doi = "10.1016/j.apnum.2019.05.022",

language = "English",

volume = "144",

pages = "140--150",

journal = "Applied Numerical Mathematics",

issn = "0168-9274",

publisher = "Elsevier",

}

TY - JOUR

T1 - Reconstruction of jointly sparse vectors via manifold optimization

AU - Petrosyan, Armenak

AU - Tran, Hoang

AU - Webster, Clayton

PY - 2019/10

Y1 - 2019/10

N2 - In this paper, we consider the challenge of reconstructing jointly sparse vectors from linear measurements. Firstly, we show that by utilizing the rank of the output data matrix we can reduce the problem to a full column rank case. This result reveals a reduction in the computational complexity of the original problem and enables a simple implementation of joint sparse recovery algorithms for full-rank setting. Secondly, we propose a new method for joint sparse recovery in the form of a non-convex optimization problem on a non-compact Stiefel manifold. In our numerical experiments our method outperforms the commonly used ℓ2,1 minimization in the sense that much fewer measurements are required for accurate sparse reconstructions. We postulate this approach possesses the desirable rank aware property, that is, being able to take advantage of the rank of the unknown matrix to improve the recovery.

AB - In this paper, we consider the challenge of reconstructing jointly sparse vectors from linear measurements. Firstly, we show that by utilizing the rank of the output data matrix we can reduce the problem to a full column rank case. This result reveals a reduction in the computational complexity of the original problem and enables a simple implementation of joint sparse recovery algorithms for full-rank setting. Secondly, we propose a new method for joint sparse recovery in the form of a non-convex optimization problem on a non-compact Stiefel manifold. In our numerical experiments our method outperforms the commonly used ℓ2,1 minimization in the sense that much fewer measurements are required for accurate sparse reconstructions. We postulate this approach possesses the desirable rank aware property, that is, being able to take advantage of the rank of the unknown matrix to improve the recovery.

KW - Huber regularization

KW - Joint sparsity

KW - Manifold optimization

KW - Non-compact Stiefel manifold

KW - Non-convex optimization

UR - https://www.scopus.com/pages/publications/85066239136

U2 - 10.1016/j.apnum.2019.05.022

DO - 10.1016/j.apnum.2019.05.022

M3 - Article

AN - SCOPUS:85066239136

SN - 0168-9274

VL - 144

SP - 140

EP - 150

JO - Applied Numerical Mathematics

JF - Applied Numerical Mathematics

ER -

Reconstruction of jointly sparse vectors via manifold optimization

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this