Sampling algorithms for l2 regression and applications

ABSTRACT

We present and analyze a sampling algorithm for the basic linear-algebraic problem of l2 regression. The l2 regression (or least-squares fit) problem takes as input a matrix A ∈ R^n×d (where we assume n ≫ d) and a target vector b ∈ Rⁿ, and it returns as output Z = minx∈R^d |b - Ax|2. Also of interest is xopt = A+b, where A⁺ is the Moore-Penrose generalized inverse, which is the minimum-length vector achieving the minimum. Our algorithm randomly samples r rows from the matrix A and vector b to construct an induced l2 regression problem with many fewer rows, but with the same number of columns. A crucial feature of the algorithm is the nonuniform sampling probabilities. These probabilities depend in a sophisticated manner on the lengths, i.e., the Euclidean norms, of the rows of the left singular vectors of A and the manner in which b lies in the complement of the column space of A. Under appropriate assumptions, we show relative error approximations for both Z and xopt. Applications of this sampling methodology are briefly discussed.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: R. Bhatia. Matrix Analysis. Springer-Verlag, New York, 1997.
• 3: Kenneth L. Clarkson, Subgradient and sampling algorithms for l1 regression, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: P. Drineas, R. Kannan, and M. W. Mahoney. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. Technical Report YALEU/DCS/TR-1269, Yale University Department of Computer Science, New Haven, CT, February 2004. Accepted for publication in the SIAM Journal on Computing.
• 5: P. Drineas, R. Kannan, and M. W. Mahoney. Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix. Technical Report YALEU/DCS/TR-1270, Yale University Department of Computer Science, New Haven, CT, February 2004. Accepted for publication in the SIAM Journal on Computing.
• 6: P. Drineas, R. Kannan, and M. W. Mahoney. Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition. Technical Report YALEU/DCS/TR-1271, Yale University Department of Computer Science, New Haven, CT, February 2004. Accepted for publication in the SIAM Journal on Computing.
• 7: P. Drineas and M. W. Mahoney. A randomized algorithm for a tensor-based generalization of the Singular Value Decomposition. Technical Report YALEU/DCS/TR-1327, Yale University Department of Computer Science, New Haven, CT, June 2005.
• 8: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 9: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast monte-carlo algorithms for finding low-rank approximations, Journal of the ACM (JACM), v.51 n.6, p.1025-1041, November 2004 [doi>10.1145/1039488.1039494]
• 10: G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
• 11: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 12: S. Sathiya Keerthi , Dennis DeCoste, A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs, The Journal of Machine Learning Research, 6, p.341-361, 9/1/2005
• 13: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 14: M. Z. Nashed, editor. Generalized Inverses and Applications. Academic Press, New York, 1976.
• 15: L. Rademacher, S. Vempala, and G. Wang. Matrix approximation and projective clustering via iterative sampling. Technical Report MIT-LCS-TR-983, Massachusetts Institute of Technology, Cambridge, MA, March 2005.
• 16: M. Rudelson and R. Vershynin. Approximation of matrices. manuscript.
• 17: G. W. Stewart and J. G. Sun. Matrix Perturbation Theory. Academic Press, New York, 1990.
• 18: R. Vershynin. Coordinate restrictions of linear operators in ln2. manuscript.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Least squares approximation

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

General Terms:
Algorithms, Theory