Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-8616
Main Title: Simultaneous Structures in Convex Signal Recovery—Revisiting the Convex Combination of Norms
Author(s): Kliesch, Martin
Szarek, Stanislaw J.
Jung, Peter
Type: Article
Language Code: en
Abstract: In compressed sensing one uses known structures of otherwise unknown signals to recover them from as few linear observations as possible. The structure comes in form of some compressibility including different notions of sparsity and low rankness. In many cases convex relaxations allow to efficiently solve the inverse problems using standard convex solvers at almost-optimal sampling rates. A standard practice to account for multiple simultaneous structures in convex optimization is to add further regularizers or constraints. From the compressed sensing perspective there is then the hope to also improve the sampling rate. Unfortunately, when taking simple combinations of regularizers, this seems not to be automatically the case as it has been shown for several examples in recent works. Here, we give an overview over ideas of combining multiple structures in convex programs by taking weighted sums and weighted maximums. We discuss explicitly cases where optimal weights are used reflecting an optimal tuning of the reconstruction. In particular, we extend known lower bounds on the number of required measurements to the optimally weighted maximum by using geometric arguments. As examples, we discuss simultaneously low rank and sparse matrices and notions of matrix norms (in the “square deal” sense) for regularizing for tensor products. We state an SDP formulation for numerically estimating the statistical dimensions and find a tensor case where the lower bound is roughly met up to a factor of two.
URI: https://depositonce.tu-berlin.de/handle/11303/9571
http://dx.doi.org/10.14279/depositonce-8616
Issue Date: 28-May-2019
Date Available: 1-Jul-2019
DDC Class: 510 Mathematik
Subject(s): compressed sensing
low rank
sparse
matrix
tensor
reconstruction
statistical dimension
convex relaxation
Sponsor/Funder: DFG, 414044773, Open Access Publizieren 2019 - 2020 / Technische Universität Berlin
EC/H2020/665778/EU/SUPPORTING MOBILITY IN THE ERA THROUGH AN INTERNATIONAL FELLOWSHIP PROGRAMME FOR DEVELOPEMENT OF BASIC RESEARCH IN POLAND/POLONEZ
License: https://creativecommons.org/licenses/by/4.0/
Journal Title: Frontiers in Applied Mathematics and Statistics
Publisher: Frontiers Media
Publisher Place: Lausanne
Volume: 5
Article Number: 23
Publisher DOI: 10.3389/fams.2019.00023
EISSN: 2297-4687
Appears in Collections:FG Theoretische Grundlagen der Kommunikationstechnik » Publications

Files in This Item:
File Description SizeFormat 
fams-05-00023.pdf1.34 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons