Constructive Algorithms for Nonlinear Sparse Approximation

Definitions and mathematical statement

The supplied question is: How can one devise effective constructive algorithms for nonlinear sparse approximation, including $m$-term approximation with respect to bases and redundant dictionaries?

A standard normed-space interpretation can be described parametrically as follows; these parameters are not specified by the source. Let $X$ be a normed vector space over $\mathbb K\in\{{\mathbb{R}},{\mathbb{C}}\}$, and let $\mathcal D\subseteq X$ be a collection of approximation elements. For $m\in{\mathbb{N}}$, $m\geq1$, define \[ \Sigma_m(\mathcal D)=\left\{\sum_{j=1}^{r}a_jg_j:0\leq r\leq m,\ a_j\in\mathbb K,\ g_j\in\mathcal D\right\}, \qquad \sigma_m(f;\mathcal D)_X=\inf_{s\in\Sigma_m(\mathcal D)}\|f-s\|_X. \] The empty sum is zero. An $m$-term constructive approximation procedure would produce coefficients and dictionary elements specifying an output $A_m(f)\in\Sigma_m(\mathcal D)$. This definition does not assume that the infimum defining $\sigma_m$ is attained. A redundant dictionary can admit distinct coefficient representations of the same vector; the source also explicitly includes approximation with respect to bases.

The research question is to devise effective constructive procedures for such nonlinear sparse approximation. The source does not specify the space, scalar field, norm, admissible input class, dictionary assumptions, meaning of basis, input representation, access to dictionary elements, computational model, or required accuracy and computational cost. In particular, it supplies no required inequality relating $\|f-A_m(f)\|_X$ to $\sigma_m(f;\mathcal D)_X$. Consequently, the displayed definitions provide a conventional framework for the question, not a uniquely determined theorem or a universal algorithmic assertion. A precise existence or performance statement requires these unresolved specifications.

Short English statement

The question asks for practical constructive methods that approximate an object using at most $m$ elements of a basis or redundant dictionary. The source leaves the approximation setting and the meaning of effectiveness unspecified, so it states a broad research objective rather than a single quantified conjecture.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002946$, title: Constructive Algorithms for Nonlinear Sparse Approximation; collection: Oberwolfach Reports Open Problems; exact source problem code: catalogue entry. The registry labels the statement exact and its status open; these are supplied classifications, not independently verified conclusions.
• Supplied source citation: Applied Harmonic Analysis and Sparse Approximation (2016), Oberwolfach Reports, DOI 10.4171/owr/2015/38, pp. 2189--2263. Supplied source URL and literature-source link, labeled "original OWR report": https://doi.org/10.4171/owr/2015/38. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. No individual proposer is identified.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the question open and describes it as a broad foundational question about constructive nonlinear approximation methods, rather than a single theorem with a definitive resolution. It lists the original OWR report as its checked source. This is supplied dated curation, not an independently verified literature assessment; time-sensitive status and cited claims require independent verification.
• The registry gives proposed year $2015$, while the supplied report title contains $2016$ and its DOI contains $2015$. These source details are retained without resolving their chronology.