Finding a sparse vector in a subspace: Linear sparsity using alternating directions
We consider the problem of recovering the sparsest vector in a subspace S ∈ R p with dim (S) = n. This problem can be considered a homogeneous variant of the sparse recovery problem, and finds applications in sparse dictionary learning, sparse PCA, and other problems in signal processing and machine learning. Simple convex heuristics for this problem provably break down when the fraction of nonzero entries in the target sparse vector substantially exceeds 1/ √ n. In contrast, we exhibit a relatively simple nonconvex approach based on alternating directions, which provably succeeds even when the fraction of nonzero entries is Ω(1). To our knowledge, this is the first practical algorithm to achieve this linear scaling. This result assumes a planted sparse model, in which the target sparse vector is embedded in an otherwise random subspace. Empirically, our proposed algorithm also succeeds in more challenging data models arising, e.g., from sparse dictionary learning.
The aim of the paper is to produce an algorithm and supporting analysis for the problem of finding a planted sparse vector in a random subspace. The paper motivates this problem as being a close relative of sparse recovery as well as having potential extensions to the dictionary learning model (in which more than one sparse vector is sought). Previous convex approaches to this problem undergo a phase transition when the number of nonzero elements in the sparse vector greatly exceed n^(-1/2). The paper finds an alternating directions based algorithm featuring a data-based initialization and an additional rounding step based on linear programming. This algorithm, in contrast to previous convex-based ones, succeeds (whp) with the target vector having a constant fraction of nonzero entries. The theoretical guarantee requires that the dimension p >= n^4 log^2 n, though empirically it seems to succeed for p linear in n. The paper produces experiments which demonstrate this linear phase transition on synthetic data, as well as showing a novel and "strange" experiment on real data demonstrating its potential role in discovering "unusual vectors" in a subspace.The paper is argued very clearly for the most part and is of high quality on its own terms. While the theoretical significance of this work is clear, the practical significance is not sufficiently clear. It is unclear to me whether the experiments on real data are of interest to practitioners. Furthermore, although the connection to dictionary learning is alluded to as a possible expansion for future works, this is not well argued for either empirically or theoretically. However, the authors have explained this connection in the rebuttal. Stronger arguments for practical importance will benefit the paper (though the authors have alluded to relations with other problems). I am not a direct expert in this particular area so I may not be able to fully appreciate its potential impact on various communities. I still find the paper very original, of high theoretical quality and even somewhat intriguing and I thus assigned the first (of two) impact scores. This was clearly the strongest paper I reviewed (among five).There are few typos that can be corrected: * "with with" in statement of Theorem 2.1 (it will also be good to define "with overwhelming probability")* Missing section reference (line 122)*(8) is not *the* Huber m-estimator over Yq (lines 137-8 are confusing).* Revise writing after first sentence of 192 (e.g., next sentence is not grammatically complete)I have read the authors' rebuttal and made very minor changes to my review. I congratulate the authors on their nice paper.