Best approximation with Walsh atoms (Q1362762)

The author connects the theoretical algorithmic approximation rate in \(L^2 (\overline R)\) for the model case where \(W\) consist of Walsh atoms. The main result stated implies that a linear combination of \(K\) atoms can be approximated to relative error \(e\) with linear combination of \(O(K^2 \log(1/E)\)-orthogonal atoms. In finite dimension \(N\), the author shows that the best approximation with \(K\) orthogonal atoms can be realized with an algorithm of order \(KN(1+\log ({N \over K}))\) and adds that a faster algorithm of order \(N\log N\) solves the problem with indirect control over \(K\). Also the author asserts that use of the term ``algorithmic'' is justified by the fact that best approximation with orthogonal atoms can be obtained by fast algorithms.