- Title
- Entropic regularization of the ℓ0 function
- Creator
- Borwein, Jonathan M.; Luke, D. Russell
- Relation
- Fixed-Point Algorithms for Inverse Problems in Science and Engineering p. 65-92
- Relation
- Springer Optimization and its Applications 49
- Publisher Link
- http://dx.doi.org/10.1007/978-1-4419-9569-8_5
- Publisher
- Springer
- Resource Type
- book chapter
- Date
- 2011
- Description
- Many problems of interest where more than one solution is possible seek, among these, the one that is sparsest. The objective that most directly accounts for sparsity, the ℓ0 metric, is usually avoided since this leads to a combinatorial optimization problem. The function ∥x∥0 is often viewed as the limit of the ℓp metrics. Naturally, there have been some attempts to use this as an objective for p small, though this is a nonconvex function for p < 1. We propose instead a scaled and shifted Fermi-Dirac entropy with two parameters, one controlling the smoothness of the approximation and the other the steepness of the metric. Our proposed metric is a convex relaxation for which a strong duality theory holds, yielding dual methods for metrics approaching the desired ∥⋅∥0 function. Without smoothing, we propose a dynamically reweighted subdifferential descent method with “exact” line search that is finitely terminating for constraints that are well-separated. This algorithm is shown to recapture in a special case certain well-known “greedy” algorithms. Consequently we are able to provide an explicit algorithm whose fixed point, under the appropriate assumptions, is the sparsest possible solution. The variational perspective yields general strategies to make the algorithm more robust.
- Subject
- convex optimization; Fenchel duality; entropy; regularization; sparsity; signal processing
- Identifier
- http://hdl.handle.net/1959.13/1038171
- Identifier
- uon:13519
- Identifier
- ISBN:9781441995681
- Rights
- The original publication is available at www.springerlink.com
- Language
- eng
- Full Text
- Hits: 1271
- Visitors: 1800
- Downloads: 183
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT03 | Author final version | 465 KB | Adobe Acrobat PDF | View Details Download |