Navegar

Colección

Datos Estadísticas

Artículo

La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

The authors introduced in previously published papers acceleration schemes for Projected Aggregation Methods (PAM), aiming at solving consistent linear systems of equalities and inequalities. They have used the basic idea of forcing each iterate to belong to the aggregate hyperplane generated in the previous iteration. That scheme has been applied to a variety of projection algorithms for solving systems of linear equalities or inequalities, proving that the acceleration technique can be successfully used for consistent problems. The aim of this paper is to extend the applicability of those schemes to the inconsistent case, employing incomplete projections onto the set of solutions of the augmented system Ax - r = b. These extended algorithms converge to the least squares solution. For that purpose, oblique projections are used and, in particular, variable oblique incomplete projections are introduced. They are defined by means of matrices that penalize the norm of the residuals very strongly in the first iterations, decreasing their influence with the iteration counter in order to fulfill the convergence conditions. The theoretical properties of the new algorithms are analyzed, and numerical experiences are presented comparing their performance with several well-known projection methods. © Springer-Verlag 2007.

Registro:

Documento: Artículo
Título:Incomplete oblique projections for solving large inconsistent linear systems
Autor:Scolnik, H.D.; Echebest, N.; Guardarucci, M.T.; Vacchino, M.C.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Ciudad Universitaria, C1428EGA Buenos Aires, Argentina
Departamento de Matemática, Facultad de Ciencias Exactas, Universidad Nacional de la Plata, La Plata, Argentina
Palabras clave:Incomplete projections; Inconsistent system; Projected Aggregation Methods; Algorithms; Convergence of numerical methods; Iterative methods; Least squares approximations; Matrix algebra; Problem solving; Incomplete projections; Inconsistent system; Linear equalities; Projected Aggregation Methods (PAM); Linear systems
Año:2008
Volumen:111
Número:1-2
Página de inicio:273
Página de fin:300
DOI: http://dx.doi.org/10.1007/s10107-006-0066-4
Título revista:Mathematical Programming
Título revista abreviado:Math. Program.
ISSN:00255610
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00255610_v111_n1-2_p273_Scolnik

Referencias:

  • Browne, J.A., Herman, G.T., Odhner, D., SNARK93: A Programming System for Image Reconstruction from Projections. Department of Radiology, University of Pennsylvania, Medical Image Processing Group (1993), Technical Report MIPG198; Byrne, C., Iterative oblique projection onto convex sets and the split feasibility problem (2002) Inverse Probl, 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) Ann. Oper. Res, 105, pp. 77-98
  • Censor, Y., Elfving, T., Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem (2002) SIAM J. Matrix Anal. Appl, 24, pp. 40-58
  • 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 Comput, 27, pp. 777-808
  • Combettes, P.L., Inconsistent signal feasibility problems: Least-squares solutions in a product space (1994) IEEE Trans. Signal Process, 42, pp. 2955-2966
  • Csiszár, I., Tusnády, G., Information geometry and alternating minimization procedures (1984) Stat. Decis. Suppl, 1, pp. 205-237
  • Echebest, N., Guardarucci, M.T., Scolnik, H.D., Vacchino, M.C., An acceleration scheme for solving convex feasibility problems using incomplete projection algorithms (2004) Numer. Algorithms, 35 (2-4), pp. 335-350
  • 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., (1980) Image Reconstruction From Projections: The Fundamentals of Computarized Tomography, , Academic, New York
  • Herman, G.T., Meyer, L.B., Algebraic reconstruction techniques can be made computationally efficient (1993) IEEE Trans. Med. 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
  • Jiang, M., Wang, G., Convergence studies on iterative Algorithms for Image Reconstruction (2003) IEEE Trans. Med. Imaging, 22, pp. 569-579
  • Kaczmarz, S.: Angenäherte Auflösung von Systemen linearer Gleichungen. Bull. Int. Acad. Pol. Sci. Lett. 35, 355-357 (1937); Landweber, L., An iteration formula for Fredholm integral equations of the first kind (1951) Am. J. Math, 73, pp. 615-624
  • Ortega, J.M., Rheinboldt, W.C., (1970) Iterative Solution of Nonlinear Equations in Several Variables, , Academic, New York, London
  • Popa, C., Extensions of Block-Projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems (1998) BIT, 38, pp. 151-176
  • Scolnik, H.D., Behebest, N., Guardarucci, M.T., Vacchino, M.C., New optimized and accelerated PAM methods for solving large non-symmetric linear systems: Theory and practice (2001) Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, Studies in Computational Mathematics, 8, pp. 457-470. , Butnariu, D, Censor, Y, Reich, S, eds, Elsevier Science Publishers, Amsterdam, The Netherlands
  • Scolnik, H.D., Behebest, N., Guardarucci, M.T., Vacchino, M.C., A class of optimized row projection methods for solving large non-symmetric linear systems (2002) Appl. Numer. Math, 41, pp. 499-513
  • Scolnik, H.D., Behebest, N., Guardarucci, M.T., Vacchino, M.C., Acceleration scheme for Parallel Projected Aggregation Methods for solving large linear systems (2002) Ann. Oper. Res, 117, pp. 95-115

Citas:

---------- APA ----------
Scolnik, H.D., Echebest, N., Guardarucci, M.T. & Vacchino, M.C. (2008) . Incomplete oblique projections for solving large inconsistent linear systems. Mathematical Programming, 111(1-2), 273-300.
http://dx.doi.org/10.1007/s10107-006-0066-4
---------- CHICAGO ----------
Scolnik, H.D., Echebest, N., Guardarucci, M.T., Vacchino, M.C. "Incomplete oblique projections for solving large inconsistent linear systems" . Mathematical Programming 111, no. 1-2 (2008) : 273-300.
http://dx.doi.org/10.1007/s10107-006-0066-4
---------- MLA ----------
Scolnik, H.D., Echebest, N., Guardarucci, M.T., Vacchino, M.C. "Incomplete oblique projections for solving large inconsistent linear systems" . Mathematical Programming, vol. 111, no. 1-2, 2008, pp. 273-300.
http://dx.doi.org/10.1007/s10107-006-0066-4
---------- VANCOUVER ----------
Scolnik, H.D., Echebest, N., Guardarucci, M.T., Vacchino, M.C. Incomplete oblique projections for solving large inconsistent linear systems. Math. Program. 2008;111(1-2):273-300.
http://dx.doi.org/10.1007/s10107-006-0066-4