Skip to main content
SpringerLink
Log in

A Frisch-Newton Algorithm for Sparse Quantile Regression

  • Original Papers
  • Published:
Acta Mathematicae Applicatae Sinica Aims and scope Submit manuscript

Abstract

Recent experience has shown that interior-point methods using a log barrier approach are far superior to classical simplex methods for computing solutions to large parametric quantile regression problems. In many large empirical applications, the design matrix has a very sparse structure. A typical example is the classical fixed-effect model for panel data where the parametric dimension of the model can be quite large, but the number of non-zero elements is quite small. Adopting recent developments in sparse linear algebra we introduce a modified version of the Frisch-Newton algorithm for quantile regression described in Portnoy and Koenker[28]. The new algorithm substantially reduces the storage (memory) requirements and increases computational speed. The modified algorithm also facilitates the development of nonparametric quantile regression methods. The pseudo design matrices employed in nonparametric quantile regression smoothing are inherently sparse in both the fidelity and roughness penalty components. Exploiting the sparse structure of these problems opens up a whole range of new possibilities for multivariate smoothing on large data sets via ANOVA-type decomposition and partial linear models.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Barrodale, I., Roberts, F. Solution of an overdetermined system of equations in the _1 norm. Communications of the ACM, 17: 319–320 (1974)

    Article  Google Scholar 

  2. Breiman, L. The Π method for estimating multivariate functions from noisy data (Disc: 145–160). Technometrics, 33: 125–143 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  3. Duff, I.S. Sparse numerical linear algebra: direct methods and preconditioning. I.S. Du., G.A. Watson (Eds.) The State of the Art in Numerical Analysis, Oxford University Press, Oxford, 27–62 1997

  4. Duff, I.S. Matrix methods. RAL-TR-1998-076, Department of Computation and Information, Rutherford Appleton Laboratory, Oxon., 1998

  5. Duff, I.S., Heroux, M.A., Pozo, R. An overview of the sparse basic linear algebra subprograms: The new standard from the BLAS technical forum. ACM Transactions on Mathematical Software, 28: 239–267 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  6. Friedman, J.H. Multivariate adaptive regression splines (Disc: 67–141). The Annals of Statistics, 19: 1–67 (1991)

    MATH  MathSciNet  Google Scholar 

  7. Frisch, R. The logarithmic potential method of convex programming. Technical Report, University Institute of Economics, Oslo, Norway, 1955

  8. Golub, H.G., van der Vorst, H.A. Closer to the solution: iterative linear solvers. I.S. Duff and G.A. Watson (Eds.), The State of the Art in Numerical Analysis, Oxford University Press, Oxford, 63–92 1997

  9. Gonzaga, C., Path-following methods for linear programming, SIAM Review, 34: 167–224 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gu, C.,Bates, D.M., Chen, Z., Wahba, G. The computation of generalized cross-validation functions through Householder tridiagonalization with applications to the .tting of interaction spline models. SIAM Journal on Matrix Analysis and Applications, 10: 457–480 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  11. Gupta, A. Recent advances in direct methods for solving unsymmetric sparse systems of linear equations. ACM Trans. Math. Software, 28: 301–324 (2002)

    Article  MATH  Google Scholar 

  12. Hansen, M., Kooperberg, C., Sardy, S. Triogram models. Journal of the American Statistical Association, 93: 101–119 (1998)

    Article  MATH  Google Scholar 

  13. Haunschmid, E.J., Ueberhuber, C.W. Direct Solvers for Sparse Systems. Tech. Report AURORA TR1999- 18, Vienna University of Technology, 1999

  14. He, X., Ng, P. COBS: qualitatively constrained smoothing via linear programming. Computational Statistics, 14: 315–337 (1999)

    Article  MATH  Google Scholar 

  15. He, X., Ng, P., Portnoy, S. Bivariate Quantile Smoothing Splines. J. Royal Stat. Soc., 60: 537–550 (1998)

    Article  MATH  Google Scholar 

  16. He, X., Shi, P. Bivariate tensor-product B-splines in a partly linear model. Journal of Multivariate Analysis, 58: 162–181 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  17. Karmarker, N. A new polynomial time algorithm for linear programming. Combinatorica, 4: 373–395 (1984)

    Article  MathSciNet  Google Scholar 

  18. Koenker, R., Mizera, I. Penalized triograms: Total variation regularization for bivariate smoothing. Journal of the Royal Statistical Society (B), 66: 145–163 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  19. Koenker, R., Ng, P. SparseM: a sparse matrix package for R. Journal of Statistical Software, 8: 2003

  20. Koenker, R., Ng, P. Inequality constrained quantile regression, manuscript, 2004

  21. Koenker, R., Ng, P., Portnoy, S. Quantile Smoothing Splines. Biometrika, 81, 673–80 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  22. Koenker, R., d’Orey, V. Computing regression quantiles. Applied Statistics, 36: 383–393 (1987)

    Article  Google Scholar 

  23. Koenker, R., d’Orey V. A remark on algorithm AS 229: Computing dual regression quantiles and regression rank scores. Applied Statistics, 43: 410–414 (1994)

    Article  Google Scholar 

  24. Liu, J. W-H. Modi.cation of the minimum degree algorithm by multiple elimination. ACM Trans. Math. Software, 11: 141–153 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  25. Lustig, I.J., Marsten, R.E., Shanno, D.F. On implementing Mehrotra’s predictor-corrector interior-point method for linear programming. SIAM Journal of Optimization, 2435–449 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  26. Lustig, I.J., Marsten, R.E., Shanno, D.F. Interior point methods for linear programming: Computational state of the art. ORSA Journal on Computing, 6: 1–14 (1994)

    MATH  MathSciNet  Google Scholar 

  27. Ng, E.G., Peyton, B.W. Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. Sci. Comput., 14: 1034–1056 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  28. Portnoy, S., Koenker, R. The Gaussian hare and the Laplacian tortoise: computability of squared-error vs absolute error estimators, (with discussions). Statistical Science, 12: 279–300 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  29. Saad, Y. Sparskit: A basic tool kit for sparse matrix computations, Version 2, available from (1994) www.cs.umn.edu/Research/arpa/SPARSKIT/sparskit.html

  30. Saad, Y., van der Vorst, H. Iterative solution of linear systems in the 20-th century. Journal of Computational and Applied Mathematics, 123: 1–33 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  31. Wright, S. Primal-Dual Interior-Point Methods. Society for Industrial and Applied Mathematics, Philadelphia, 1997

Download references

Author information

Authors and Affiliations

  1. Department of Economics, University of Illinois at Urbana-Champaign, IL 61820, USA

    Roger Koenker

  2. College of Business Administration, Northern Arizona University, 70 McConnell Dr, 15066, Flagstaff, AZ 86011-5066, USA

    Pin Ng

Authors
  1. Roger Koenker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pin Ng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Roger Koenker.

Additional information

This research was partially supported by NSF grant SES-02-40781.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Koenker, R., Ng, P. A Frisch-Newton Algorithm for Sparse Quantile Regression. Acta Mathematicae Applicatae Sinica, English Series 21, 225–236 (2005). https://doi.org/10.1007/s10255-005-0231-1

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10255-005-0231-1

Keywords

2000 MR Subject Classification

Search

Navigation