Fast greedy algorithms for dictionary selection with generalized sparsity constraints
In dictionary selection, several atoms are selected from finite candidates that successfully approximate given data points in the sparse representation. We propose a novel efficient greedy algorithm for dictionary selection. Not only does our algorithm work much faster than the known methods, but it can also handle more complex sparsity constraints, such as average sparsity. Using numerical experiments, we show that our algorithm outperforms the known methods for dictionary selection, achieving competitive performances with dictionary learning algorithms in a smaller running time.
This paper proposes an algorithm for the dictionary selection problem.  In this problem the goal is to find a small subset of "atoms" so it possible to approximate the whole data using the selected subset in sparse representation. The proposed algorithm is an extension to "Replacement Greedy", an algorithm for two-stage submodular maximization. This is a similar problem to the paper's problem, however the underline function in this paper is not submodular. The algorithm uses techniques in Orthogonal matching pursuit (OMP). This technique allows them to provably improve the running time of the algorithm and be able to pose global constraints. Experimental results show improvement in runtime and tests residual variance in comparison with other existing algorithms. The technical parts appear to be correct. -In the experiment section, the author used test residual variance to compare between the algorithms. I don’t understand why? Isn't it better comparing the value of the computed subset? After all the goal is to maximize this function. In my opinion, I think the authors should at least explain their choice.  -The algorithm requires the smooth parameter M_{s,2}, this parameter can be bounded. According to the author, this value can be computed in O(n^2 * d) time. This sounds much higher than the run time of this algorithm and other existing algorithms. What am I missing? -The paper is generally well written and constructed. There was one notation that I think could at least be explained better- equation (5) the \_Z_t'\Z_t. It took me a while to understand it. -The p-replacement definition was a little bit confusing. At first I thought it is just a chain of replacement, that in each step approaches (Z_1*...Z_t*). It is possible to write a small explanation before the definition. -An intuition for line 179-180 is needed. "we propose a proxy of this quantity by borrowing an idea from orthogonal matching pursuit".  -The main contribution of this paper, in my opinion, is the extension of OMP, which gives a better runtime and the possibility to pose global constraints.  -The paper also proposes an online variant of their algorithm. This variant is the end of the supplementary, which I didn’t fully verify.  -It seems the paper has shown better  results on the dictionary selection problem both in theory and application.      Other comments and typos:  -Table 1: The approximation ratio of the replacement greedy is from your paper. I think it should be stated somewhere in the caption.  -Typo Eq(3)- You should replace the big T with small t: Z_t' \subset Z_t+a.   -Line 370 in the supplementary: "there exists a bijection"- what is the properties of this bijection? Maybe it is clear from the context but I still think you should add it.   ---Edit---- I have read the author response. The clarification about the upper bounds of M_{s,2}  satisfied me (the second comment). Therefore, I am updating my rating of this paper from 6 to 7.