Abstract
Two optimal orthogonalization processes are devised to orthogonalize, possibly approximately, the columns of a very large and possibly sparse matrix A ∈ ℂn×k. Algorithmically the aim is, at each step, to optimally decrease nonorthogonality of all the columns of A. One process relies on using translated small rank corrections. Another is a polynomial orthogonalization process for performing the Löwdin orthogonalization. The steps rely on using iterative methods combined, preferably, with preconditioning which can have a dramatic effect on how fast nonorthogonality decreases. The speed of orthogonalization depends on how bunched the singular values of A are, modulo the number of steps taken. These methods put the steps of the Gram-Schmidt orthogonalization process into perspective regarding their (lack of) optimality. The constructions are entirely operator theoretic and can be extended to infinite dimensional Hilbert spaces.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Argyros S, Haydon R. A hereditarily indecomposable Loo-space that solves the scalar-plus-compact problem. Acta Math, 2011, 206: 1–54
Björck A. Numerical Methods for Least Squares Problems. Philadelphia: SIAM, 1996
Brualdi R, Friedland S, Pothen A. The sparse basis problem and multilinear algebra. SIAM J Matrix Anal Appl, 1995, 16: 1–20
Businger P, Golub G. Linear least squares solutions by Householder transformations. Numer Math, 1965, 7: 269–276
Christensen O. Frames, Riesz bases, and discrete Gabor/wavelet expansions. Bull Amer Math Soc (NS), 2001, 38: 273–291
Dahlquist G, Bjorck A. Numerical Methods in Scientific Computing. Vol. I. Philadelphia: SIAM, 2008
Douglas R G, Liaw C. A geometric approach to finite rank unitary perturbations. Indiana Univ Math J, 2013, 62: 333–354
Feichtinger H, Luef F, Werther T. A guided tour from linear algebra to the foundations of Gabor analysis. In: Gabor and Wavelet Frames. IMS Lecture Notes Series, vol. 10. Hackensack: World Scientific, 2007, 1–49
Frank M, Paulsen V, Tiballi T. Symmetric approximation of frames and bases in Hilbert spaces. Trans Amer Math Soc, 2002, 354: 777–793
Garoni C, Speleers H, Ekström S-E, et al. Symbol-based analysis of finite element and isogeometric B-spline discretizations of eigenvalue problems: Exposition and review. Arch Comput Meth Eng, 2018, 26: 1639–1690
Gerstenhaber M. On nilalgebras and linear varieties of nilpotent matrices. I. Amer J Math, 1958, 80: 614–622
Goldstein J A, Levy M. Linear algebra and quantum chemistry. Amer Math Monthly, 1991, 98: 710–718
Golub G, Varah J. On the characterization of the best ℓ2-scaling of a matrix. SIAM J Numer Anal, 1974, 11: 472–479
Hansen A C. On the approximation of spectra of linear Hilbert space operators. PhD Thesis. Cambridge: University of Cambridge, 2008
Higham N. Accuracy and Stability of Numerical Algorithms, 2nd ed. Philadelphia: SIAM, 2002
Horn R A, Johnson C R. Topics in Matrix Analysis. Cambridge: Cambridge University Press, 1991
Horn R A, Johnson C R. Matrix Analysis, 2nd ed. Cambridge: Cambridge University Press, 2013
Huhtanen M. Factoring matrices into the product of two matrices. BIT, 2007, 47: 793–808
Huhtanen M. Energy conservation and unitary approximation numbers. J Math Phys, 2007, 48: 073512
Huhtanen M, Nevanlinna O. Polynomials and lemniscates of indefiniteness. Numer Math, 2016, 133: 233–253
Jaffard S, Young R M. A representation theorem for Schauder bases in Hilbert space. Proc Amer Math Soc, 1998, 126: 553–560
Leon S J, Bjöorck A, Gander W. Gram-Schmidt orthogonalization: 100 years and more. Numer Linear Algebra Appl, 2013, 20: 492–532
Liaw C. Rank one and finite rank perturbations–survey and open problems. arXiv:1205.4376v1, 2012
Livne O E, Golub G. Scaling by binormalization. Numer Algorithms, 2004, 35: 97–120
Löowdin P-O. On the non-orthogonality problem connected with the use of atomic wave functions in the theory of molecules and crystals. J Chem Phys, 1950, 18: 365–375
Lowdin P-O. On the nonorthogonality problem. Adv Quantum Chem, 1970, 5: 185–199
Mayer I. Simple Theorems, Proofs, and Derivations in Quantum Chemistry. New York: Kluwer, 2003
Mayer I, Surjan P R. Handling overlap as a perturbation. Croatica Chemica Acta, 1993, 66: 161–165
Olver P J, Shakiban C. Applied Linear Algebra, 2nd ed. Undergraduate Texts in Mathematics. New York: Springer, 2018
Philippe B. An algorithm to improve nearly orthonormal sets of vectors on a vector processor. SIAM J Algebraic Discrete Methods, 1987, 3: 393–403
Rubensson E H, Bock N, Holmstöom E, et al. Recursive inverse factorization. J Comput Chem, 2008, 128: 104105
Rubensson E H, Rudberg E, Salek P. Sparse matrix algebra for quantum modeling of large systems. In: Applied Parallel Computing, State of the Art in Scientific Computing. Lecture Notes in Computer Science, vol. 4699. Berlin-Heidelberg: Springer, 2007
Saad Y. Iterative Methods for Sparse Linear Systems, 2nd ed. Philadelphia: SIAM, 2003
Strang G. Piecewise polynomials and the finite element method. Bull Amer Math Soc, 1973, 79: 1128–1137
Szabo A, Ostlund N S. Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory. Mineola: Dover, 1996
Szczepanik D, Mrozek J. On several alternatives for Loöwdin orthogonalization. Comput Theor Chem, 2013, 1008: 103–109
Thijssen J. Computational Physics, 2nd ed. Cambridge: Cambridge University Press, 2007
van der Sluis A. Condition numbers and equilibration of matrices. Numer Math, 1975, 14: 14–23
Varah J. On the condition number of local bases for piecewise cubic polynomials. Math Comp, 1977, 137: 37–44
Walk P, Jung P. Approximation of Lowdin orthogonalization to a spectrally efficient orthogonal overlapping PPM design for UWB impulse radio. Signal Processing, 2012, 92: 649–666
Acknowledgements
This work was supported by the Academy of Finland (Grant No. 288641). The authors are grateful to the anonymous referees for their comments and suggestions which led to corrections of some mistakes and improved the paper notably.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Huhtanen, M., Uusitalo, P. Optimal orthogonalization processes. Sci. China Math. 65, 203–220 (2022). https://doi.org/10.1007/s11425-018-1711-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-018-1711-x
Keywords
- optimal orthogonalization
- sparse matrix
- Gram-Schmidt orthogonalization
- Lowdin orthogonalization
- polynomial orthogonalization
- implicit orthogonalization
- preconditioning
- Gram matrix
- frame inequality