Algorithms for subset selection in linear regression

ABSTRACT

We study the problem of selecting a subset of k random variables to observe that will yield the best linear prediction of another variable of interest, given the pairwise correlations between the observation variables and the predictor variable. Under approximation preserving reductions, this problem is equivalent to the "sparse approximation" problem of approximating signals concisely. The subset selection problem is NP-hard in general; in this paper, we propose and analyze exact and approximation algorithms for several special cases of practical interest. Specifically, we give an FPTAS when the covariance matrix has constant bandwidth, and exact algorithms when the associated covariance graph, consisting of edges for pairs of variables with non-zero correlation, forms a tree or has a large (known) independent set. Furthermore, we give an exact algorithm when the variables can be embedded into a line such that the covariance decreases exponentially in the distance, and a constant-factor approximation when the variables have no "conditional suppressor variables". Much of our reasoning is based on perturbation results for the R² multiple correlation measure, which is frequently used as a natural measure for "goodness-of-fit statistics". It lies at the core of our FPTAS, and also allows us to extend our exact algorithms to approximation algorithms when the matrix "nearly" falls into one of the above classes. We also use our perturbation analysis to prove approximation guarantees for the widely used "Forward Regression" heuristic under the assumption that the observation variables are nearly independent.

REFERENCES

• 1: K. Anstreicher, M. Fampa, J. Lee, and J. Williams. An exact algorithm for maximum entropy sampling. Operations Research, 43(4):684--691, 1995.
• 2: Kurt M. Anstreicher , Marcia Fampa , Jon Lee , Joy Williams, Maximum-entropy remote sampling, Discrete Applied Mathematics, v.108 n.3, p.211-226, March 15, 2001 [doi>10.1016/S0166-218X(00)00217-1]
• 3: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 4: E. J. Candes, J. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59:1207--1223, 2005.
• 5: W. Cochran. Some effects of errors of measurement on multiple correlation. Journal of the American Statistical Association, 65(329):22--34, 1970.
• 6: J. Cohen and P. Cohen. Applied multiple regression/correlation analysis for the behavioral sciences. Lawrence Erlbaum Assoc Publishers, 2003.
• 7: G. Cornuejols, M. Fisher, and G. Nemhauser. Location of bank accounts to optimize float. Management Science, 23:789--810, 1977.
• 8: Christophe Couvreur , Yoram Bresler, On the Optimality of the Backward Greedy Algorithm for the Subset Selection Problem, SIAM Journal on Matrix Analysis and Applications, v.21 n.3, p.797-808, Feb.-March 2000 [doi>10.1137/S0895479898332928]
• 9: G. Davis, S. Mallat, and M. Avellaneda. Greedy adaptive approximation. Journal of Constructive Approximation, 13:57--98, 1997.
• 10: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 11: G. Diekhoff. Statistics for the Social and Behavioral Sciences. Wm. C. Brown Publishers, 2002.
• 12: D. Donoho. For most large underdetermined systems of linear equations, the minimal 11-norm near-solution approximates the sparsest near-solution. Communications on Pure and Applied Mathematics, 59:1207--1223, 2005.
• 13: D. L. Donoho, M. Elad, and V. N. Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transaction on Information Theory, 52:6--18, 2006.
• 14: V. F. Flack and P. C. Chang. Frequency of selecting noise variables in subset regression analysis: A simulation study. The American Statistician Journal, 41(1):84--86, 1987.
• 15: Anna C. Gilbert , S. Muthukrishnan , Martin J. Strauss, Approximation of functions over redundant dictionaries using coherence, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 16: Carlos Guestrin , Andreas Krause , Ajit Paul Singh, Near-optimal sensor placements in Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.265-272, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102385]
• 17: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 18: Frank K. Hwang , Shmuel Onn , Uriel G. Rothblum, A Polynomial Time Algorithm for Shaped Partition Problems, SIAM Journal on Optimization, v.10 n.1, p.70-81, 1999 [doi>10.1137/S1052623497344002]
• 19: R. A. Johnson , D. W. Wichern, Applied multivariate statistical analysis, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 20: P. Liaskovitis and C. Schurgers. Leveraging redundancy in sampling-interpolation applications for sensor networks. In Proc. 3rd Intl. Conf. on Distributed Computing in Sensor Systems, 2007.
• 21: A. Miller. Subset Selection in Regression. Chapman and Hall, second edition, 2002.
• 22: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 23: B. K. Natarajan, Sparse Approximate Solutions to Linear Systems, SIAM Journal on Computing, v.24 n.2, p.227-234, April 1995 [doi>10.1137/S0097539792240406]
• 24: G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265--294, 1978.
• 25: Shmuel Onn , Leonard J. Schulman, The Vector Partition Problem for Convex Objective Functions, Mathematics of Operations Research, v.26 n.3, p.583-590, August 2001 [doi>10.1287/moor.26.3.583.10587]
• 26: M. H. Pesaran and R. J. Smith. A generalized r2 criterion for regression models estimated by the instrumental variables method. Econometrica, 62(3):705--710, 1994.
• 27: J. Saxe. Dynamic programming algorithms for recognizing small bandwidth graphs in polynomial time. SIAM Journal on Algebraic Methods I, 1(4):363--369, 1980.
• 28: G. W. Stewart and J.G. Sun. Matrix Perturbation Theory. Academic Press, 1990.
• 29: V. N. Temlyakov, Greedy algorithms and M-term approximation with regard to redundant dictionaries, Journal of Approximation Theory, v.98 n.1, p.117-145, May 1999 [doi>10.1006/jath.1998.3265]
• 30: V. Temlyakov. Nonlinear methods of approximation. Foundations of Computational Mathematics, 3:33--107, 2002.
• 31: R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of Royal Statistical Society, 58:267--288, 1996.
• 32: J. Tropp. Greed is good: algorithmic results for sparse approximation. IEEE Trans. Information Theory, 50:2231--2242, 2004.
• 33: J. Tropp. Topics in Sparse Approximation. PhD thesis, University of Texas, Austin, 2004.
• 34: J. Tropp. Just relax: Convex programming methods for identifying sparse signals. IEEE Trans. Information Theory, 51:1030--1051, 2006.
• 35: J. Tropp, A. Gilbert, S. Muthukrishnan, and M. Strauss. Improved sparse approximation over quasi-incoherent dictionaries. In Proc. IEEE-ICIP, 2003.
• 36: W. F. Velicer. Suppressor variables and the semipartial correlation coefficient. Educational and Psychological Measurement, 38:953--958, 1978.
• 37: M. Wainwright. Sharp thresholds for noisy and high-dimensional recovery of sparsity using l1-constrained quadratic programming. In Proc. Allerton Conference on Communication, 2006.
• 38: D. A. Walker. Suppressor variable(s) importance within a regression model. Journal of College Student Development, 44:127--133, 2003.
• 39: H. Zou and T. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society, Series B, 67(2):301--320, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
sparse approximation, subset selection