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.
Bibliographical noteFunding 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.