Subspace Selection for Projection Maximization With Matroid Constraints

DOI10.1109/TSP.2016.2634544zbMATH Open1414.94743arXiv1507.04822OpenAlexW2964046134MaRDI QIDQ4620661

Author name not available (Why is that?)

Publication date: 8 February 2019

Published in: (Search for Journal in Brave)

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 non-uniform matroid constraints, respectively. We show that if the elements in the ground set are mutually orthogonal, then these algorithms are optimal when the matroid is uniform and they achieve at least $1/2$-approximations of the optimal solution when the matroid is non-uniform.

Full work available at URL: https://arxiv.org/abs/1507.04822

Mathematics Subject Classification ID

No records found.

This page was built for publication: Subspace Selection for Projection Maximization With Matroid Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620661)