Metric entropy and sparse linear approximation of ℓ q-hulls for 0 < q ≤ 1

Fuchang Gao, Ching Kang Ing, Yuhong Yang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Consider ℓ q-hulls, 0 < q ≤ 1, from a dictionary of M functions in L p space for 1 ≤ p < ∞. Their precise metric entropy orders are derived. Sparse linear approximation bounds are obtained to characterize the number of terms needed to achieve accurate approximation of the best function in a ℓ q-hull that is closest to a target function. Furthermore, in the special case of p = 2, it is shown that a weak orthogonal greedy algorithm achieves the optimal approximation under an additional condition.

Original languageEnglish (US)
Pages (from-to)42-55
Number of pages14
JournalJournal of Approximation Theory
Issue number1
StatePublished - Feb 2013

Bibliographical note

Funding Information:
The authors thank Chiao-Yi Yang and Wei-Ying Wu for helpful discussions. The work of Fuchang Gao was supported in part by a grant from the Simons Foundation ( #246211 ). The work of Ching-Kang Ing was supported in part by the Academia Sinica Investigator Award . The work of Yuhong Yang was supported by funding from NSC of Taiwan, the University of Minnesota and NSF of USA . He thanks the Institute of Statistical Science at the Academia Sinica for their hospitality during his visit. Comments and suggestions by three referees are greatly appreciated for improving the paper.


Dive into the research topics of 'Metric entropy and sparse linear approximation of ℓ <sub>q</sub>-hulls for 0 < q ≤ 1'. Together they form a unique fingerprint.

Cite this