Pass-Efficient Unsupervised Feature Selection
The goal of unsupervised feature selection is to identify a small number of important features that can represent the data. We propose a new algorithm, a modification of the classical pivoted QR algorithm of Businger and Golub, that requires a small number of passes over the data. The improvements are based on two ideas: keeping track of multiple features in each pass, and skipping calculations that can be shown not to affect the final selection. Our algorithm selects the exact same features as the classical pivoted QR algorithm, and has the same favorable numerical stability. We describe experiments on real-world datasets which sometimes show improvements of several orders of magnitude over the classical algorithm. These results appear to be competitive with recently proposed randomized algorithms in terms of pass efficiency and run time. On the other hand, the randomized algorithms may produce more accurate features, at the cost of small probability of failure.
This paper proposes improvements to the classical 
      pivoted QR algorithm ("QRP") which lead to time and space advantages 
      useful for feature selection in the large p setting (many variables). The 
      paper is well-written for the most part, and the presentation is clear 
      enough. The algorithm proposed in the paper follows from what might be 
      called low-hanging (or even "obvious") improvements to QRP, in the sense 
      that anyone working with large datasets in practice would begin to think 
      about these and related ideas. But, as in many practical settings, the 
      devil is in the details, and *details matter* particularly in large-scale 
      implementations. This is where the submission shines. The authors have 
      been careful about their CPU and memory bookkeeping at every step, and 
      additionally give a few nice low-level suggestions (e.g., efficient data 
      structures to consider; stability of orthogonalization subroutines is 
      discussed, etc.). On the whole this paper provides a detailed, thorough 
      picture for practitioners working with large datasets, and this is perhaps 
      its most salient selling point: one can go from the paper directly to 
      implementation. I believe this is enough of an advantage to overcome 
      concerns about novelty and the other complaints outlined below. 
      Other comments: - The interpolative decomposition is closely 
      related, but it not cited let alone reviewed or compared. This is perhaps 
      a major omission. Yes, the ID is also related to CUR decompositions, which 
      are mentioned, but let's not assume the reader knows this, or by 
      extension, how it ultimately relates to the IQRP algorithm proposed in the 
      paper. See: - Work from Mark Tygert (NYU) - N. Halko, P. G. 
      Martinsson, and J. A. Tropp, "Finding Structure with Randomness: 
      Probabilistic Algorithms for Constructing Approximate Matrix 
      Decompositions," SIAM Review, 2011. - The ID and other randomized 
      techniques are reasonably efficient. So, if we're going to compare 
      randomized algorithms to IQRP, the efficiency advantage of the latter 
      seems to critically hinge on c being less than k. Why should c be 
      substantially less than k? There is no discussion really exploring this 
      critical, even key, distinction. The experiments suggest it may be true, 
      but the empirical evaluation is limited, and might make it hard to form a 
      concrete opinion as to whether one can expect c << k in a given 
      practical setting going forward. Note that this is apparently what 
      underpins the question as to whether to use IQRP over randomized ID, for 
      instance. - Experiments: major improvements are needed. For what 
      is mainly an applications/practical paper, the empirical evaluation is a 
      bit underwhelming. Could you show QRP perhaps on the same plots at a 
      minimum? Or comparisons to other, more competitive baselines one would 
      actually consider if faced with making a design decision? - What 
      is meant by "randomization algorithms can produce better features"? This 
      statement is never really made precise. Also you say "IQRP may be less 
      accurate". In terms of what? It would be interesting to see the accuracy 
      on the regression/classification problems themselves, using the features 
      selected by the various algorithms. Ultimately, this is what we're after, 
      at least for the datasets considered in the paper. - There are 
      other, related, applications for the pivoted QR decomposition that may 
      help your case. For example, finding nearly dependent columns in forward 
      stepwise regression techniques (and computing related statistics: F-stats, 
      t-stats etc).