The best \(m\)-term approximation and greedy algorithms (Q1127004): Difference between revisions

The author proves two theorems on nonlinear \(m\)-term approximation in \(L_p, 1<p<\infty\). The first one says that if a basis \(\Psi:=\{\psi_I\}_I\) is \(L_p\)-equivalent to the Haar basis then a near best \(m\)-term approximation to any \(f\in L_p\) may be realized by the following simple greedy type algorithm: take the expansions \(f=\sum_Ic_I\psi_I\) and form a sum of an \(m\)-term with the largest \(\| c_I\psi_I\|_p\) out of this expansion. The second one states that nonlinear approximations with regard to two dictionaries: the Haar basis and the set of all characteristic functions of intervals are equivalent in a very strong sense.