{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:09:06Z","timestamp":1772042946349,"version":"3.50.1"},"reference-count":47,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T00:00:00Z","timestamp":1715644800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A double optimal solution (DOS) of a least-squares problem Ax=b,A\u2208Rq\u00d7n with q\u2260n is derived in an m+1-dimensional varying affine Krylov subspace (VAKS); two minimization techniques exactly determine the m+1 expansion coefficients of the solution x in the VAKS. The minimal-norm solution can be obtained automatically regardless of whether the linear system is consistent or inconsistent. A new double optimal algorithm (DOA) is created; it is sufficiently time saving by inverting an m\u00d7m positive definite matrix at each iteration step, where m\u226amin(n,q). The properties of the DOA are investigated and the estimation of residual error is provided. The residual norms are proven to be strictly decreasing in the iterations; hence, the DOA is absolutely convergent. Numerical tests reveal the efficiency of the DOA for solving least-squares problems. The DOA is applicable to least-squares problems regardless of whether q&lt;n or q&gt;n. The Moore\u2013Penrose inverse matrix is also addressed by adopting the DOA; the accuracy and efficiency of the proposed method are proven. The m+1-dimensional VAKS is different from the traditional m-dimensional affine Krylov subspace used in the conjugate gradient (CG)-type iterative algorithms CGNR (or CGLS) and CGRE (or Craig method) for solving least-squares problems with q&gt;n. We propose a variant of the Karush\u2013Kuhn\u2013Tucker equation, and then we apply the partial pivoting Gaussian elimination method to solve the variant, which is better than the original Karush\u2013Kuhn\u2013Tucker equation, the CGNR and the CGNE for solving over-determined linear systems. Our main contribution is developing a double-optimization-based iterative algorithm in a varying affine Krylov subspace for effectively and accurately solving least-squares problems, even for a dense and ill-conditioned matrix A with q\u226an or q\u226bn.<\/jats:p>","DOI":"10.3390\/a17050211","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T03:20:29Z","timestamp":1715656829000},"page":"211","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Solving Least-Squares Problems via a Double-Optimal Algorithm and a Variant of the Karush\u2013Kuhn\u2013Tucker Equation for Over-Determined Systems"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6366-3539","authenticated-orcid":false,"given":"Chein-Shan","family":"Liu","sequence":"first","affiliation":[{"name":"Center of Excellence for Ocean Engineering, National Taiwan Ocean University, Keelung 20224, Taiwan"}]},{"given":"Chung-Lun","family":"Kuo","sequence":"additional","affiliation":[{"name":"Center of Excellence for Ocean Engineering, National Taiwan Ocean University, Keelung 20224, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9846-0694","authenticated-orcid":false,"given":"Chih-Wen","family":"Chang","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, National United University, Miaoli 36063, Taiwan"}]}],"member":"1968","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"ref_1","first-page":"175","article-title":"An optimal multi-vector iterative algorithm in a Krylov subspace for solving the ill-posed linear inverse problems","volume":"33","author":"Liu","year":"2013","journal-title":"Comput. Mater. Contin."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/MCISE.2000.814652","article-title":"Guest editors\u2019 introduction to the top 10 algorithms","volume":"2","author":"Dongarra","year":"2000","journal-title":"Comput. Sci. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/nla.499","article-title":"Recent computational developments in Krylov subspace methods for linear systems","volume":"14","author":"Simoncini","year":"2007","journal-title":"Numer. Linear Alg. Appl."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"856","DOI":"10.1137\/0907058","article-title":"GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems","volume":"7","author":"Saad","year":"1986","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1090\/S0025-5718-1981-0616364-6","article-title":"Krylov subspace methods for solving large unsymmetric linear systems","volume":"37","author":"Saad","year":"1981","journal-title":"Math. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01385726","article-title":"QMR: A quasi-minimal residual method for non-Hermitian linear systems","volume":"60","author":"Freund","year":"1991","journal-title":"Numer. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1137\/S0895479802403459","article-title":"Inexact Krylov subspace methods for linear systems","volume":"26","author":"Sleijpen","year":"2004","journal-title":"SIAM J. Matrix Ana. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"409","DOI":"10.6028\/jres.049.044","article-title":"Methods of conjugate gradients for solving linear systems","volume":"49","author":"Hestenes","year":"1952","journal-title":"J. Res. Nat. Bur. Stand."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.6028\/jres.049.006","article-title":"Solution of systems of linear equations by minimized iterations","volume":"49","author":"Lanczos","year":"1952","journal-title":"J. Res. Nat. Bur. Stand."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1137\/0712047","article-title":"Solution of sparse indefinite systems of linear equations","volume":"12","author":"Paige","year":"1975","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Fletcher, R. (1976). Conjugate Gradient Methods for Indefinite Systems, Springer. Lecture Notes in Math.","DOI":"10.1007\/BFb0080116"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1137\/0910004","article-title":"CGS: A fast Lanczos-type solver for nonsymmetric linear systems","volume":"10","author":"Sonneveld","year":"1989","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1137\/0913035","article-title":"Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems","volume":"13","year":"1992","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-0427(00)00412-X","article-title":"Iterative solution of linear systems in the 20th century","volume":"123","author":"Saad","year":"2000","journal-title":"J. Comput. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Saad, Y. (2003). Iterative Methods for Sparse Linear Systems, SIAM. [2nd ed.].","DOI":"10.1137\/1.9780898718003"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"van der Vorst, H.A. (2003). Iterative Krylov Methods for Large Linear Systems, Cambridge University Press.","DOI":"10.1017\/CBO9780511615115"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1007\/BF01436075","article-title":"Numerical methods for solving linear least squares problems","volume":"7","author":"Golub","year":"1965","journal-title":"Numer. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1810","DOI":"10.1137\/100787921","article-title":"MINRES-QLP: A Krylov subspace method for indefinite or singular symmetric systems","volume":"33","author":"Choi","year":"2011","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1604","DOI":"10.1016\/j.cam.2010.08.042","article-title":"Iterative method for computing Moore-Penrose inverse based on Penrose equations","volume":"235","author":"Petkovic","year":"2011","journal-title":"J. Comput. Appl. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.cam.2014.01.034","article-title":"Two improvements of the iterative method for computing Moore-Penrose inverse based on Penrose equations","volume":"267","author":"Petkovic","year":"2014","journal-title":"J. Comput. Appl. Math."},{"key":"ref_21","first-page":"9828","article-title":"An improved method for the computation of the Moore-Penrose inverse matrix","volume":"217","author":"Katsikis","year":"2011","journal-title":"Appl. Math. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1016\/j.aml.2011.09.051","article-title":"Computation of generalized inverse by using the LDL* decomposition","volume":"25","author":"Stanimirovic","year":"2012","journal-title":"Appl. Math. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1269","DOI":"10.2298\/FIL1307269S","article-title":"An iterative method to compute Moore-Penrose inverse based on gradient maximal convergence rate","volume":"27","author":"Sheng","year":"2013","journal-title":"Filomat"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/j.cam.2008.10.008","article-title":"A new method for computing Moore-Penrose inverse matrices","volume":"228","author":"Toutounian","year":"2009","journal-title":"J. Comput. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1016\/j.apnum.2020.06.014","article-title":"On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems","volume":"157","author":"Zhang","year":"2020","journal-title":"Appl. Numer. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"101092","DOI":"10.1016\/j.jocs.2020.101092","article-title":"A note on parallel approximate pseudoinverse matrix techniques for solving linear least squares problems","volume":"41","author":"Lipitakis","year":"2020","journal-title":"J. Comput. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"107057","DOI":"10.1016\/j.aml.2021.107057","article-title":"A new randomized Gauss\u2013Seidel method for solving linear least-squares problems","volume":"116","author":"Niu","year":"2021","journal-title":"Appl. Math. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.laa.2020.09.006","article-title":"Algorithms for indefinite linear least squares problems","volume":"623","author":"Bojanczyk","year":"2021","journal-title":"Linear Algebra Appli."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"107689","DOI":"10.1016\/j.aml.2021.107689","article-title":"On the convergence of a randomized block coordinate descent algorithm for a matrix least squares problem","volume":"124","author":"Du","year":"2022","journal-title":"Appl. Math. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"110095","DOI":"10.1016\/j.automatica.2021.110095","article-title":"Iterative pre-conditioning for expediting the distributed gradient-descent method: The case of linear least-squares problem","volume":"137","author":"Chakrabarti","year":"2022","journal-title":"Automatica"},{"key":"ref_31","first-page":"127892","article-title":"Splitting-based randomized iterative methods for solving indefinite least squares problem","volume":"446","author":"Zhang","year":"2023","journal-title":"Appl. Math. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"108780","DOI":"10.1016\/j.aml.2023.108780","article-title":"A projection method for general form linear least-squares problems","volume":"145","author":"Pes","year":"2023","journal-title":"Appl. Math. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"114954","DOI":"10.1016\/j.cam.2022.114954","article-title":"An index search method based inner-outer iterative algorithm for solving nonnegative least squares problems","volume":"424","author":"Kuo","year":"2023","journal-title":"J. Comput. Appl. Math."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"102029","DOI":"10.1016\/j.jocs.2023.102029","article-title":"Greedy double subspaces coordinate descent method for solving linear least-squares problems","volume":"70","author":"Jin","year":"2023","journal-title":"J. Comput. Sci."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"108654","DOI":"10.1016\/j.compchemeng.2024.108654","article-title":"Solving least-squares problems in directed networks: A distributed approach","volume":"185","author":"Jahvani","year":"2024","journal-title":"Comput. Chem. Eng."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"127631","DOI":"10.1016\/j.jmaa.2023.127631","article-title":"Matrix representations of multivalued projections and least squares problems","volume":"530","author":"Contino","year":"2024","journal-title":"J. Math. Anal. Appl."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/BF02163027","article-title":"Singular value decomposition and least squares solutions","volume":"14","author":"Golub","year":"1970","journal-title":"Numer. Math."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rck, A. (1996). Numerical Methods for Least Squares Problems, SIAM Publisher.","DOI":"10.1137\/1.9781611971484"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/j.cam.2013.10.013","article-title":"A doubly optimized solution of linear equations system expressed in an affine Krylov subspace","volume":"260","author":"Liu","year":"2014","journal-title":"J. Comput. Appl. Math."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.enganabound.2014.04.017","article-title":"Optimal algorithms in a Krylov subspace for solving linear inverse problems by MFS","volume":"44","author":"Liu","year":"2014","journal-title":"Eng. Anal. Bound. Elem."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1080\/17415977.2014.880905","article-title":"A double optimal descent algorithm for iteratively solving ill-posed linear inverse problems","volume":"23","author":"Liu","year":"2015","journal-title":"Inv. Prob. Sci. Eng."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1998","DOI":"10.1016\/j.camwa.2014.04.011","article-title":"A maximal projection solution of ill-posed linear system in a column subspace, better than the least squares solution","volume":"67","author":"Liu","year":"2014","journal-title":"Comput. Math. Appl."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Papez, J., and Tichy, P. (2024). Estimating error norms in CG-like algorithms for least-squares and least-norm problems. Numer. Algorithms, 1\u201328.","DOI":"10.1007\/s11075-023-01691-x"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/s10543-024-01015-y","article-title":"Bounded perturbations resilient iterative methods for linear systems and least squares problems: Operator-based approaches, analysis, and performance evaluation","volume":"64","author":"Abbasi","year":"2024","journal-title":"BIT Numer. Math."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1162\/NECO_a_00549","article-title":"A novel iterative method for computing generalized inverse","volume":"26","author":"Xia","year":"2014","journal-title":"Neural Comput."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.enganabound.2014.01.011","article-title":"On the ill-conditioning of the MFS for irregular boundary data with sufficient regularity","volume":"41","author":"Feng","year":"2014","journal-title":"Eng. Anal. Bound. Elem."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.enganabound.2015.09.003","article-title":"A multiple-scale Pascal polynomial triangle solving elliptic equations and inverse Cauchy problems","volume":"62","author":"Liu","year":"2016","journal-title":"Eng. Anal. Bound. Elem."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/211\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:41:51Z","timestamp":1760107311000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,14]]},"references-count":47,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,5]]}},"alternative-id":["a17050211"],"URL":"https:\/\/doi.org\/10.3390\/a17050211","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,14]]}}}