Bias Versus Non-Convexity in Compressed Sensing
(2022) In Journal of Mathematical Imaging and Vision 64(4). p.379-394- Abstract
- Cardinality and rank functions are ideal ways of regularizing under-determined linear systems, but optimization of the resulting formulations is made difficult since both these penalties are non-convex and discontinuous. The most common remedy is to instead use the ℓ1- and nuclear norms. While these are convex and can therefore be reliably optimized, they suffer from a shrinking bias that degrades the solution quality in the presence of noise. This well-known drawback has given rise to a fauna of non-convex alternatives, which usually features better global minima at the price of maybe getting stuck in undesired local minima. We focus in particular penalties based on the quadratic envelope, which have been shown to have global minima which... (More)
- Cardinality and rank functions are ideal ways of regularizing under-determined linear systems, but optimization of the resulting formulations is made difficult since both these penalties are non-convex and discontinuous. The most common remedy is to instead use the ℓ1- and nuclear norms. While these are convex and can therefore be reliably optimized, they suffer from a shrinking bias that degrades the solution quality in the presence of noise. This well-known drawback has given rise to a fauna of non-convex alternatives, which usually features better global minima at the price of maybe getting stuck in undesired local minima. We focus in particular penalties based on the quadratic envelope, which have been shown to have global minima which even coincide with the “oracle solution,” i.e., there is no bias at all. So, which one do we choose, convex with a definite bias, or non-convex with no bias but less predictability? In this article, we develop a framework which allows us to interpolate between these alternatives; that is, we construct sparsity inducing penalties where the degree of non-convexity/bias can be chosen according to the specifics of the particular problem. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/79382c1c-2f49-4e66-9fd6-3e3010b79f91
- author
- Gerosa, Daniele LU ; Carlsson, Marcus LU and Olsson, Carl LU
- organization
- publishing date
- 2022
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Compressed sensing, Quadratic envelopes, Non-convex optimization
- in
- Journal of Mathematical Imaging and Vision
- volume
- 64
- issue
- 4
- pages
- 379 - 394
- publisher
- Springer
- external identifiers
-
- scopus:85128495579
- ISSN
- 1573-7683
- DOI
- 10.1007/s10851-022-01071-5
- language
- English
- LU publication?
- yes
- id
- 79382c1c-2f49-4e66-9fd6-3e3010b79f91
- date added to LUP
- 2022-03-14 18:03:24
- date last changed
- 2023-05-11 07:53:26
@article{79382c1c-2f49-4e66-9fd6-3e3010b79f91,
abstract = {{Cardinality and rank functions are ideal ways of regularizing under-determined linear systems, but optimization of the resulting formulations is made difficult since both these penalties are non-convex and discontinuous. The most common remedy is to instead use the ℓ1- and nuclear norms. While these are convex and can therefore be reliably optimized, they suffer from a shrinking bias that degrades the solution quality in the presence of noise. This well-known drawback has given rise to a fauna of non-convex alternatives, which usually features better global minima at the price of maybe getting stuck in undesired local minima. We focus in particular penalties based on the quadratic envelope, which have been shown to have global minima which even coincide with the “oracle solution,” i.e., there is no bias at all. So, which one do we choose, convex with a definite bias, or non-convex with no bias but less predictability? In this article, we develop a framework which allows us to interpolate between these alternatives; that is, we construct sparsity inducing penalties where the degree of non-convexity/bias can be chosen according to the specifics of the particular problem.}},
author = {{Gerosa, Daniele and Carlsson, Marcus and Olsson, Carl}},
issn = {{1573-7683}},
keywords = {{Compressed sensing; Quadratic envelopes; Non-convex optimization}},
language = {{eng}},
number = {{4}},
pages = {{379--394}},
publisher = {{Springer}},
series = {{Journal of Mathematical Imaging and Vision}},
title = {{Bias Versus Non-Convexity in Compressed Sensing}},
url = {{http://dx.doi.org/10.1007/s10851-022-01071-5}},
doi = {{10.1007/s10851-022-01071-5}},
volume = {{64}},
year = {{2022}},
}