Optimal Sparse Linear Encoders and Sparse PCA
Principal components analysis (PCA) is the optimal linear encoder of data. Sparse linear encoders (e.g., sparse PCA) produce more interpretable features that can promote better generalization. (i) Given a level of sparsity, what is the best approximation to PCA? (ii) Are there efficient algorithms which can achieve this optimal combinatorial tradeoff? We answer both questions by providing the first polynomial-time algorithms to construct optimal sparse linear auto-encoders; additionally, we demonstrate the performance of our algorithms on real data.
The paper considers the problem of designing “sparse linear encoders”, i.e., a linear transformation to obtain a low dimensional representation of the input data that preserves as much information as possible while satisfying additional sparsity constraints. In particular, consider a d-by-k matrix H whose columns have at most r nonzero entries. Every d-dimensional data point x is represented by a k-dimensional (encoded) vector z = H’x. The matrix H is the “encoder”. For a given H, we can also specify a “decoder” G, that maps points from k dimensions back to the original d-dimensional space, while minimizing the loss over all datapoints: ||X-XHG||_F (points are rows of X). The question is then how to design the optimal sparse encoder H.  The main result is an algorithm for designing a sparse linear encoder H, using an existing algorithm for the Column Subset Selection problem as a black box. The authors establish a reduction and are able to give approximation guarantees for the linear encoding problem based on the guarantees of the CSS algorithm.  They also propose an alternative approach based on the same algorithm, but computing the components (columns) of the encoder one by one. They also provide the first theoretical analysis (i.e. approximation guarantees) for this case as well.  They conclude with experiments comparing their approach against existing approaches for sparse PCA which focus on the objective of maximizing variance. They show that the two objectives can result to different linear encoders which is interesting.   
The paper has an interesting theoretical contribution.  The objective of obtaining a low-dimensional representation of the data that minimizes a Frobenius representation error is common. The paper draws connections of the above problem with sparse PCA showing that it can be seen in fact as a generalization of the latter. The authors also have a useful discussion explaining the above “loss minimization” objective differs from (and is perhaps of greater interest to the ML community compared to) the “explained variance maximization” viewpoint for PCA (even though the two objectives are equivalent in the case of  PCA).  As mentioned above, the authors propose an algorithm for designing a sparse linear encoder utilizing a reduction to the CSS problem and using an existing CSS algorithm as a black box. The obtained linear encoder has the restriction (or property) that all k dimensions (columns of H) have the same r nonzero coordinates. The theoretical guarantees are interesting. The main theorem (Thm 7) gives a multiplicative factor guarantee for the expected achieved error with a factor that depends on the choice of the sparsity parameter r. For instance, the theorem implies that for sparsity r = Omega(k/epsilon), the linear encoder achieves a low-dimensional representation with error comparable to the best (unconstrained) rank-k approximation.  The lower bound in Thm 8 also nicely supplements the previous result. The subsequent segment sketching the proof of Thm 8 could be improved. Among others, what is B and Y in Lemma 9?  In section 3, the authors describe that their approach can be used to compute the k columns of H sequentially and also provide theoretical approximation guarantees. Of course the analysis of the sequential/greedy approach is more challenging and those guarantees are much weaker compared to those for the batch algorithm. For example, the error bound in Thm 11 includes an additive term that depends on the sum of the top singular values sigma_2^2 +...+ sigma_\ell^2. This error term would scale proportionally with the dimension of the input data. Does the “small additive term” in the subsequent comments refer to this error term?  They conclude with experiments comparing their algorithm with algorithms for sparse PCA. They show that their algorithms gives low dimensional representations with lower reconstruction (Frob) error, but perform worse with respect to the “variance” metric, supporting the claim that the two objectives result in different encoders.  Minor: Line 48: sentence ends at the comma. In the comments under Thm 7, there is a stray “2.” Lines 159-160 seem to repeat the comment in 155. “Matrrial” in line 212