American Institute of Mathematical Sciences

Advanced
December  2020, 10(4): 451-461. doi: 10.3934/naco.2020044

An improved algorithm for generalized least squares estimation

Xiao-Wen Chang 1,, and  David Titley-Peloquin 2,

1. 

School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 0E9
2. 

Department of Bioresource Engineering, McGill University, Ste-Anne-de-Bellevue, Quebec, Canada, H9X 3V9

* Corresponding author

Received  May 2020 Revised  September 2020 Published  September 2020

Fund Project: This work was supported in part by NSERC of Canada Grant RGPIN-2017-0513

The textbook direct method for generalized least squares estimation was developed by Christopher C. Paige about 40 years ago. He proposed two algorithms. Suppose that the noise covariance matrix, rather than its factor, is available. Both of the Paige's algorithms involve three matrix factorizations. The first does not exploit the matrix structure of the problem, but it can be implemented by blocking techniques to reduce data communication time on modern computer processors. The second takes advantage of the matrix structure, but its main part cannot be implemented by blocking techniques. In this paper, we propose an improved algorithm. The new algorithm involves only two matrix factorizations, instead of three, and can be implemented by blocking techniques. We show that, in terms of flop counts, the improved algorithm costs less than Paige's first algorithm in any case and less than his second algorithm in some cases. Numerical tests show that in terms of CPU running time, our improved algorithm is faster than both of the existing algorithms when blocking techniques are used.

Keywords: Generalized least squares estimation, numerical algorithms, matrix factorizations, blocking, efficiency.
Mathematics Subject Classification: Primary: 62J05, 65F20; Secondary: 15A23; 93E24.
Citation: Xiao-Wen Chang, David Titley-Peloquin. An improved algorithm for generalized least squares estimation. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 451-461. doi: 10.3934/naco.2020044
References:
[1]

E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney and D. Sorensen, LAPACK Users' Guide, SIAM, Philadelphia, PA, Third Edition, 1999. doi: 10.1137/1.9780898718201.  Google Scholar

[2]

Jeff Bezanson, Alan Edelman, Stefan Karpinski and Viral B Shah, Julia: A fresh approach to numerical computing, SIAM Review, 59 (2017), 65-98.  doi: 10.1137/141000671.  Google Scholar

[3]

Ǻ. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, PA, 1996. Google Scholar

[4]

Ǻ. Björck, Numerical Methods in Matrix Computations, Springer, Philadelphia, PA, 2015. Google Scholar

[5] G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, Maryland, 4th edition, 2013.   Google Scholar
[6]

S. Kourouklis and C. C. Paige, A constrained least squares approach to the general Gauss-Markov linear model, Journal of the American Statistical Association, 76 (1981), 620-625.   Google Scholar

[7]

C. C. Paige, Computer solution and perturbation analysis of generalized linear least squares problems, Math. Comput., 33 (1979), 171-183.  doi: 10.2307/2006034.  Google Scholar

[8]

C. C. Paige, Fast numerically stable computations for generalized linear least squares problems, SIAM J. Num. Anal., 16 (1979), 165-171.  doi: 10.1137/0716012.  Google Scholar

[9]

R. Schreiber and C. Van Loan, A storage efficient WY representation for products of Householder transformations, SIAM J. of Sci. Stat. Computing, 10 (1991), 53-57.  doi: 10.1137/0910005.  Google Scholar

show all references

References:
[1]

E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney and D. Sorensen, LAPACK Users' Guide, SIAM, Philadelphia, PA, Third Edition, 1999. doi: 10.1137/1.9780898718201.  Google Scholar

[2]

Jeff Bezanson, Alan Edelman, Stefan Karpinski and Viral B Shah, Julia: A fresh approach to numerical computing, SIAM Review, 59 (2017), 65-98.  doi: 10.1137/141000671.  Google Scholar

[3]

Ǻ. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, PA, 1996. Google Scholar

[4]

Ǻ. Björck, Numerical Methods in Matrix Computations, Springer, Philadelphia, PA, 2015. Google Scholar

[5] G. H. Golub and C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, Maryland, 4th edition, 2013.   Google Scholar
[6]

S. Kourouklis and C. C. Paige, A constrained least squares approach to the general Gauss-Markov linear model, Journal of the American Statistical Association, 76 (1981), 620-625.   Google Scholar

[7]

C. C. Paige, Computer solution and perturbation analysis of generalized linear least squares problems, Math. Comput., 33 (1979), 171-183.  doi: 10.2307/2006034.  Google Scholar

[8]

C. C. Paige, Fast numerically stable computations for generalized linear least squares problems, SIAM J. Num. Anal., 16 (1979), 165-171.  doi: 10.1137/0716012.  Google Scholar

[9]

R. Schreiber and C. Van Loan, A storage efficient WY representation for products of Householder transformations, SIAM J. of Sci. Stat. Computing, 10 (1991), 53-57.  doi: 10.1137/0910005.  Google Scholar

Figure 6.1.  Average CPU running time per solve over $10$ solves for $ \mathbf{A}\in {\mathbb{R}}^{m \times n}$ with $n = 80$, $m = 100:200:3500$
Figure Options

Download full-size image

Download as PowerPoint slide

Table201 
Algorithm 1:

1: Compute the QL factorization of $ \mathbf{A} $: $ \mathbf{H}_n\cdots \mathbf{H}_1 \mathbf{A}= \begin{bmatrix} {\boldsymbol{0}} \mathbf{L}_{ \mathbf{A}} \end{bmatrix} $
2: Compute $ \bar {\boldsymbol{\Sigma}}= \mathbf{H}_1\cdots \mathbf{H}_n {\boldsymbol{\Sigma}} \mathbf{H}_n\cdots \mathbf{H}_1 $
3: Compute $ \tilde {\mathbf{y}} = \mathbf{H}_1\cdots \mathbf{H}_n {\mathbf{y}} $
4: Compute the Cholesky factorization of $ \bar {\boldsymbol{\Sigma}} $: $ \bar {\boldsymbol{\Sigma}}= \mathbf{L} \mathbf{L}^ {\mkern-1.5mu\mathsf{T}} $
5: Solve $ \mathbf{L}(1\!:\!n,1\!:\!n) {\mathbf{z}}_1 = \tilde {\mathbf{y}}(1\!:\!n) $ for $ {\mathbf{z}}_1 $
6: Solve $ \mathbf{L}_{ \mathbf{A}} {\hat{\mathbf{x}}}=\tilde {\mathbf{y}}(n+1:m)- \mathbf{L}(n+1\!:\!m,1\!:\!n) {\mathbf{z}}_1 $ for $ {\hat{\mathbf{x}}} $
Table Options

Download as excel

Algorithm 1:

1: Compute the QL factorization of $ \mathbf{A} $: $ \mathbf{H}_n\cdots \mathbf{H}_1 \mathbf{A}= \begin{bmatrix} {\boldsymbol{0}} \mathbf{L}_{ \mathbf{A}} \end{bmatrix} $
2: Compute $ \bar {\boldsymbol{\Sigma}}= \mathbf{H}_1\cdots \mathbf{H}_n {\boldsymbol{\Sigma}} \mathbf{H}_n\cdots \mathbf{H}_1 $
3: Compute $ \tilde {\mathbf{y}} = \mathbf{H}_1\cdots \mathbf{H}_n {\mathbf{y}} $
4: Compute the Cholesky factorization of $ \bar {\boldsymbol{\Sigma}} $: $ \bar {\boldsymbol{\Sigma}}= \mathbf{L} \mathbf{L}^ {\mkern-1.5mu\mathsf{T}} $
5: Solve $ \mathbf{L}(1\!:\!n,1\!:\!n) {\mathbf{z}}_1 = \tilde {\mathbf{y}}(1\!:\!n) $ for $ {\mathbf{z}}_1 $
6: Solve $ \mathbf{L}_{ \mathbf{A}} {\hat{\mathbf{x}}}=\tilde {\mathbf{y}}(n+1:m)- \mathbf{L}(n+1\!:\!m,1\!:\!n) {\mathbf{z}}_1 $ for $ {\hat{\mathbf{x}}} $
[1]

Ya-Xiang Yuan. Recent advances in numerical methods for nonlinear equations and nonlinear least squares. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 15-34. doi: 10.3934/naco.2011.1.15
[2]

Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030
[3]

Chengjin Li. Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 511-520. doi: 10.3934/naco.2020048
[4]

Enrique Fernández-Cara, Arnaud Münch. Numerical null controllability of semi-linear 1-D heat equations: Fixed point, least squares and Newton methods. Mathematical Control & Related Fields, 2012, 2 (3) : 217-246. doi: 10.3934/mcrf.2012.2.217
[5]

Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043
[6]

Hassan Mohammad, Mohammed Yusuf Waziri, Sandra Augusta Santos. A brief survey of methods for solving nonlinear least-squares problems. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 1-13. doi: 10.3934/naco.2019001
[7]

Mila Nikolova. Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inverse Problems & Imaging, 2008, 2 (1) : 133-149. doi: 10.3934/ipi.2008.2.133
[8]

Enrico Gerlach, Charlampos Skokos. Comparing the efficiency of numerical techniques for the integration of variational equations. Conference Publications, 2011, 2011 (Special) : 475-484. doi: 10.3934/proc.2011.2011.475
[9]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791
[10]

Pengyu Yan, Shi Qiang Liu, Cheng-Hu Yang, Mahmoud Masoud. A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking. Journal of Industrial & Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040
[11]

Yanfei Lu, Qingfei Yin, Hongyi Li, Hongli Sun, Yunlei Yang, Muzhou Hou. Solving higher order nonlinear ordinary differential equations with least squares support vector machines. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1481-1502. doi: 10.3934/jimo.2019012
[12]

JaEun Ku. Maximum norm error estimates for Div least-squares method for Darcy flows. Discrete & Continuous Dynamical Systems - A, 2010, 26 (4) : 1305-1318. doi: 10.3934/dcds.2010.26.1305
[13]

Lucian Coroianu, Danilo Costarelli, Sorin G. Gal, Gianluca Vinti. Approximation by multivariate max-product Kantorovich-type operators and learning rates of least-squares regularized regression. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4213-4225. doi: 10.3934/cpaa.2020189
[14]

Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070
[15]

Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020350
[16]

H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175
[17]

Karl Peter Hadeler. Michaelis-Menten kinetics, the operator-repressor system, and least squares approaches. Mathematical Biosciences & Engineering, 2013, 10 (5&6) : 1541-1560. doi: 10.3934/mbe.2013.10.1541
[18]

Runchang Lin, Huiqing Zhu. A discontinuous Galerkin least-squares finite element method for solving Fisher's equation. Conference Publications, 2013, 2013 (special) : 489-497. doi: 10.3934/proc.2013.2013.489
[19]

Ai-Guo Wu, Ying Zhang, Hui-Jie Sun. Parametric Smith iterative algorithms for discrete Lyapunov matrix equations. Journal of Industrial & Management Optimization, 2020, 16 (6) : 3047-3063. doi: 10.3934/jimo.2019093
[20]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

 Impact Factor: 

Tools

Metrics

  • PDF downloads (21)
  • HTML views (45)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences