Average performance of the sparsest approximation using a general dictionary. (English) Zbl 1243.68313
The model under study is the sparsest approximation of a data \(d \in \mathbb{R}^{N}\) using a given \(N\times M\) real-valued matrix \(A\) with \(N \geq M\) and \(\mathrm{rank}(A)=N\). The sparsest approximation of \(d\) is any solution of the following optimization problem:
\[
(P_{d}): \quad \min \ell_{0}(u), \quad \text{under the constraint}\quad \|Au - d\| \leq \tau,
\]
where \(\|\cdot\|\) is a given norm on \(\mathbb{R}^{N}\), \(\tau > 0\) is a tolerance parameter, and for any \(u \in (u_{1},\dots ,u_{M})\in R^{M}\) set \(\ell_{0}(u) = \overline{\{i\in \{1,\dots ,M \}; u_{i}\neq 0 \}}\), where the “overbar” means cardinality. To solve \((P_{d})\) the authors propose a method that they call APA (average performance in approximation). The aim is to estimate the distribution law of \(\mathrm{val}(P_{d})\) (a solution to \((P_{d})\)) knowing statistical properties of \(d\).
Problems of the sparsest approximation arise in signal and image processing in context of compression.
Problems of the sparsest approximation arise in signal and image processing in context of compression.
Reviewer: Wiesław Kotarski (Sosnowiec)
MSC:
| 68U10 | Computing methodologies for image processing |
| 41A25 | Rate of convergence, degree of approximation |
| 65D15 | Algorithms for approximation of functions |
| 49K30 | Optimality conditions for solutions belonging to restricted classes (Lipschitz controls, bang-bang controls, etc.) |
| 90C27 | Combinatorial optimization |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
approximation; best \(K\)-term approximation; constrained minimization; dictionary; estimation; measure theory; nonconvex functions; nonsmooth functions; sparse representationSoftware:
CoSaMPReferences:
| [1] | Besag J.E., J. R. Stat. Soc. B 48 pp 259– (1986) |
| [2] | DOI: 10.1080/02664768900000049 · doi:10.1080/02664768900000049 |
| [3] | DOI: 10.1016/j.acha.2009.04.002 · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002 |
| [4] | DOI: 10.1137/060657704 · Zbl 1178.68619 · doi:10.1137/060657704 |
| [5] | DOI: 10.1090/S0894-0347-08-00610-3 · Zbl 1206.94008 · doi:10.1090/S0894-0347-08-00610-3 |
| [6] | DOI: 10.1109/18.119732 · Zbl 0849.94005 · doi:10.1109/18.119732 |
| [7] | DOI: 10.1137/S003614450037906X · Zbl 0979.94010 · doi:10.1137/S003614450037906X |
| [8] | DOI: 10.1109/TIT.2009.2016006 · Zbl 1367.94082 · doi:10.1109/TIT.2009.2016006 |
| [9] | DOI: 10.1007/BF02678430 · Zbl 0885.41006 · doi:10.1007/BF02678430 |
| [10] | DOI: 10.1017/S0962492900002816 · doi:10.1017/S0962492900002816 |
| [11] | Donoho D., J. R. Stat. Soci. B 54 pp 41– (1992) |
| [12] | Evans L.C., Measure Theory and Fine Properties of Functions (1992) · Zbl 0804.28001 |
| [13] | DOI: 10.1109/TIT.2005.855614 · Zbl 1286.94031 · doi:10.1109/TIT.2005.855614 |
| [14] | DOI: 10.1109/TPAMI.1984.4767596 · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596 |
| [15] | DOI: 10.1007/BF00054839 · doi:10.1007/BF00054839 |
| [16] | DOI: 10.1007/978-4-431-66933-3 · doi:10.1007/978-4-431-66933-3 |
| [17] | Luenberger D., Optimization by Vector Space Methods (, 1. ed. (1969) · Zbl 0176.12701 |
| [18] | DOI: 10.1109/78.258082 · Zbl 0842.94004 · doi:10.1109/78.258082 |
| [19] | DOI: 10.1016/j.acha.2008.07.002 · Zbl 1163.94003 · doi:10.1016/j.acha.2008.07.002 |
| [20] | DOI: 10.1007/s10208-008-9031-3 · Zbl 1183.68739 · doi:10.1007/s10208-008-9031-3 |
| [21] | DOI: 10.1109/ACSSC.1993.342465 · doi:10.1109/ACSSC.1993.342465 |
| [22] | DOI: 10.1017/CBO9780511662454 · doi:10.1017/CBO9780511662454 |
| [23] | DOI: 10.1109/TIP.2007.904975 · doi:10.1109/TIP.2007.904975 |
| [24] | DOI: 10.1109/TIT.2004.834793 · Zbl 1288.94019 · doi:10.1109/TIT.2004.834793 |
| [25] | DOI: 10.1109/TIT.2005.864420 · Zbl 1288.94025 · doi:10.1109/TIT.2005.864420 |
| [26] | DOI: 10.1109/TIT.2007.909108 · Zbl 1288.94022 · doi:10.1109/TIT.2007.909108 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
