Name
Abstract | ||
|---|---|---|
Suppose that there is a ground set which consists of a large number of vectors in a Hilbert space. Consider the problem of selecting a subset of the ground set such that the projection of a vector of interest onto the subspace spanned by the vectors in the chosen subset reaches the maximum norm. This problem is generally NP-hard, and alternative approximation algorithms such as forward regression and orthogonal matching pursuit have been proposed as heuristic approaches. In this paper, we investigate bounds on the performance of these algorithms by introducing the notions of elemental curvatures. More specifically, we derive lower bounds, as functions of these elemental curvatures, for performance of the aforementioned algorithms with respect to that of the optimal solution under uniform and nonuniform matroid constraints, respectively. We show that if the elements in the ground set are mutually orthogonal, then these algorithms are optimal in terms of achieving the largest projection when the matroid is uniform and they achieve at least a fraction of 1/2 of the optimal solution when the matroid is nonuniform. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/TSP.2016.2634544 | IEEE Trans. Signal Processing |
Keywords | DocType | Volume |
Matching pursuit algorithms,Signal processing algorithms,Approximation algorithms,Electronic mail,Cramer-Rao bounds,Greedy algorithms,Linear programming | Journal | 65 |
Issue | ISSN | Citations |
5 | 1053-587X | 0 |
PageRank | References | Authors |
0.34 | 23 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhenliang Zhang | 1 | 101 | 15.69 |
| yuan wang | 2 | 0 | 0.34 |
| Edwin K. P. Chong | 3 | 1758 | 185.45 |
| Ali Pezeshki | 4 | 450 | 38.31 |
| Louis L. Scharf | 5 | 2525 | 414.45 |