Abstract:
The aim of this paper is to extend the applicability of an algorithm for solving inconsistent linear systems to the rank-deficient case, by employing incomplete projections onto the set of solutions of the augmented system Ax-r = b. The extended algorithm converges to the unique minimal norm solution of the least squares solutions. For that purpose, incomplete oblique projections are used, defined by means of matrices that penalize the norm of the residuals. The theoretical properties of the new algorithm are analyzed, and numerical experiences are presented comparing its performance with some well-known projection methods.
Registro:
Documento: |
Artículo
|
Título: | Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems |
Autor: | Scolnik, H.D.; Echebest, N.E.; Guardarucci, M.T. |
Filiación: | Dto. de Computación, Fac. de Ciencias Exactas y Naturales, UBA, Pabellón 1, Ciudad Universitaria, Buenos Aires C1428EGA, Argentina Departamento de Matemática, Fac. de Ciencias Exactas, UNLP, P.O. Box 172, La Plata 1900, Argentina Departamento de C. Básicas, Fac. de Ingeniería, UNLP, La Plata 1900, Argentina
|
Palabras clave: | Incomplete oblique projections; Minimal norm solution; Rank-deficient least-squares problems |
Año: | 2009
|
Volumen: | 5
|
Número: | 2
|
Página de inicio: | 175
|
Página de fin: | 191
|
DOI: |
http://dx.doi.org/10.3934/jimo.2009.5.175 |
Título revista: | Journal of Industrial and Management Optimization
|
Título revista abreviado: | J. Ind. Manage. Optim.
|
ISSN: | 15475816
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15475816_v5_n2_p175_Scolnik |
Referencias:
- Briec, W., Solonandrasana, B., (2006) Some remarks on a succesive projection sequence, Journal of Industrial and Management Optimization, 2, pp. 451-466
- J. A. Browne, G. T. Herman and D. Odhner, SNARK93: A Programming System for Image Reconstruction from Projections, Department of Radiology, University of Pennsylvania, Medical Image Processing Group, Technical Report MIPG198, 1993; Byrne, C., Iterative oblique projection onto convex sets and the split feasibility problem (2002) Inverse Problems, 18, pp. 441-453
- Byrne, C., Censor, Y., Proximity function minimization using multiple bregman projections with applications to split feasibility and Kullback-Leibler distance minimization (2001) Annals of Operations Research, 105, pp. 77-98
- Censor, Y., Eggermont, P.B., Gordon, D., Strong underrelaxation in Kaczmarz's method for inconsistent systems (1983) Numer. Math, 41, pp. 83-92
- Censor, Y., Zenios, S., (1997) Parallel Optimization: Theory and Applications, , Oxford University Press, New York
- Censor, Y., Gordon, D., Gordon, R., Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems (2001) Parallel Computing, 27, pp. 777-808
- Censor, Y., Elfving, T., Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem (2002) SIAM J. Matrix Anal. and Applicat, 24, pp. 40-58
- Combettes, P., Puh, H., Iterations of parallel convex projections in Hilbert spaces (1994) Numer. Funct. Anal. Optim, 15, pp. 225-243
- Csiszár, I., Tusnády, G., Information geometry and alternating minimization procedures (1984) Statistics and Decisions, 1 (SUPPL.EMENT), pp. 205-237
- Dolan, E.D., Moré, J.J., Benchmarking optimization software with performance profiles (2002) Mathematical Programming, 91, pp. 201-213
- Echebest, N., Guardarucci, M.T., Scolnik, H.D., Vacchino, M.C., An accelerated iterative method with diagonally scaled oblique projections for solving linear feasibility problems (2005) Annals of Operations Research, 138, pp. 235-257
- García Palomares, U.M., Parallel projected aggregation methods for solving the convex feasibility problem (1993) SIAM J. Optim, 3, pp. 882-900
- Herman, G.T., Meyer, L.B., Algebraic reconstruction techniques can be made computationally efficient (1993) IEEE Trans. Medical Imaging, 12, pp. 600-609
- Householder, A.S., Bauer, F.L., On certain iterative methods for solving linear systems (1960) Numer. Math, 2, pp. 55-59
- Kaczmarz, S., Angenäherte Auflösung von systemen linearer Gleichungen (1937) Bull. Intern. Acad. Polonaise Sci. Lett, 35, pp. 355-357
- Jiang, M., Wang, G., Convergence studies on iterative algorithms for image reconstruction (2003) IEEE Transactions on Medical Imaging, 22, pp. 569-579
- Landweber, L., An iteration formula for Fredholm integral equations of the first kind (1951) Amer. J. Math, 73, pp. 615-624
- Popa, C., Extensions of Block-Projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems (1998) BIT, 38, pp. 151-176
- Popa, C., Zdunek, R., Kaczmarz extended algorithm for tomographic image reconstruction from limited-data (2004) Mathematics and Computers in Simulation, 65, pp. 579-598
- Scolnik, H.D., Echebest, N., Guardarucci, M.T., Vacchino, M.C., A class of optimized row projection methods for solving large non-symmetric linear systems (2002) Applied Numerical Mathematics, 41, pp. 499-513
- Scolnik, H.D., Echebest, N., Guardarucci, M.T., Vacchino, M.C., Acceleration scheme for parallel projected aggregation methods for solving large linear systems (2002) Annals of Operations Research, 117, pp. 95-115
- Scolnik, H.D., Echebest, N., Guardarucci, M.T., Vacchino, M.C., Incomplete oblique projections for solving large inconsistent linear systems (2008) Mathematical Programming, Ser. B, 111, pp. 273-300
Citas:
---------- APA ----------
Scolnik, H.D., Echebest, N.E. & Guardarucci, M.T.
(2009)
. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial and Management Optimization, 5(2), 175-191.
http://dx.doi.org/10.3934/jimo.2009.5.175---------- CHICAGO ----------
Scolnik, H.D., Echebest, N.E., Guardarucci, M.T.
"Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems"
. Journal of Industrial and Management Optimization 5, no. 2
(2009) : 175-191.
http://dx.doi.org/10.3934/jimo.2009.5.175---------- MLA ----------
Scolnik, H.D., Echebest, N.E., Guardarucci, M.T.
"Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems"
. Journal of Industrial and Management Optimization, vol. 5, no. 2, 2009, pp. 175-191.
http://dx.doi.org/10.3934/jimo.2009.5.175---------- VANCOUVER ----------
Scolnik, H.D., Echebest, N.E., Guardarucci, M.T. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. J. Ind. Manage. Optim. 2009;5(2):175-191.
http://dx.doi.org/10.3934/jimo.2009.5.175