nach oben

Journal of Scientific Computing

Erschienen in:

28.11.2018

ALORA: Affine Low-Rank Approximations

verfasst von: Alan Ayala, Xavier Claeys, Laura Grigori

Erschienen in: Journal of Scientific Computing | Ausgabe 2/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we present the concept of affine low-rank approximation for an \(m\times n\) matrix, consisting in fitting its columns into an affine subspace of dimension at most \(k \ll \min (m,n)\). We present the algorithm ALORA that constructs an affine approximation by slightly modifying the application of any low-rank approximation method. We focus on approximations created with the classical QRCP and subspace iteration algorithms. For the former, we discuss existing pivoting techniques and provide a bound for the error when an arbitrary pivoting technique is used. For the case of fsubspace iteration, we prove a result on the convergence of singular vectors, showing a bound that agrees with the one recently proved for the convergence of singular values. Finally, we present numerical experiments using challenging matrices taken from different fields, showing good performance and validating the theoretical framework.

Vorheriger Artikel A High Order Semi-Lagrangian Discontinuous Galerkin Method for the Two-Dimensional Incompressible Euler Equations and the Guiding Center Vlasov Model Without Operator Splitting

Nächster Artikel Optimal Quasi-diagonal Preconditioners for Pseudodifferential Operators of Order Minus Two

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Anderson, E., Bai, Z., Bischof, C.H., Blackford, S., Demmel, J.W., Dongarra, J.J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.C.: LAPACK Users’ Guide. SIAM, Philadelphia (1999)CrossRefMATH

Bebendorf, M.: Approximation of boundary element matrices. Numer. Math. 86(4), 565–589 (2000)MathSciNetCrossRefMATH

Bebendorf, M.: Hierarchical Matrices. Springer, Leipzig (2008)MATH

Bischof, C.H.: A parallel QR factorization algorithm with controlled local pivoting. SIAM J. Matrix Anal. Appl. 12, 36–57 (1991)MathSciNetMATH

Boutsidis, C., Mahoney, M., Drineas, P.: An improved approximationalgorithm for the column subset selection problem. In: Proceedingsof the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 968–977 (2009)

Demmel, J.W., Grigori, L., Gu, M., Xiang, H.: Communication avoiding rank revealing QR factorization with column pivoting. SIAM J. Matrix Anal. Appl. 36, 55–89 (2015)MathSciNetCrossRefMATH

Drmač, Z., Bujanović, Z.: On the failure of rank-revealing QR factorization software—a case study. ACM Trans. Math. Softw. 35(2):12:1–12, 28 (2008)

Drmač, Z., Veselić, K.: New fast and accurate Jacobi SVD algorithm. I. SIAM J. Matrix Anal. Appl. 29(4), 1322–1342 (2008)MathSciNetCrossRefMATH

Drmač, Z., Veselić, K.: New fast and accurate Jacobi SVD algorithm. II. SIAM J. Matrix Anal. Appl. 29(4), 1343–1362 (2008)MathSciNetCrossRefMATH

10.

Duersch, J., Gu, M.: Randomized QR with column pivoting. SIAM J. Sci. Comput. 39(4), C263–C291 (2017)MathSciNetCrossRefMATH

11.

Eckart, G., Young, G.: The approximation of one matrix by another of lower rank. Psychometrica 1, 211–218 (1936)CrossRefMATH

12.

Edelman, A.: Eigenvalues and condition numbers of random matrices. SIAM J. Matrix Anal. Appl. 9(4), 543–560 (1988)MathSciNetCrossRefMATH

13.

Frieze, A., Kannan, R., Vempala, S.: Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6), 1025–1041 (2004)MathSciNetCrossRefMATH

14.

Golub, G.H., Klema, V., Stewart, G.W.: Rank degeneracy and least squares problems. Tech. Report TR-456, Department of. Computer Science, University of Maryland, College Park, MD (1976)

15.

Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Jonhs Hopkins University Press, Baltimore (1996)MATH

16.

Grigori, L., Cayrols, S., Demmel, J.: Low rank approximation of a sparse matrix based on lu factorization with column and row tournament pivoting. SIAM J. Sci. Comput. 40(2), C181–C209 (2018)MathSciNetCrossRefMATH

17.

Gu, M.: Subspace iteration randomization and singular value problems. SIAM J. Sci. Comput. 37(3), A1139–A1173 (2015)MathSciNetCrossRefMATH

18.

Gu, M., Eisenstat, S.: Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM J. Matrix Anal. Appl. 17(4), 848–869 (1996)MathSciNetMATH

19.

Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011)MathSciNetCrossRefMATH

20.

Hansen, P.C.: Regularization tools version 4.1 for MATLAB 7.3. http://www.imm.dtu.dk/~pcha/Regutools. Accessed 10 Oct (2018)

21.

Horn, R., Johnson, C.: Topics in Matrix Analysis. Cambridge University Press, New York (1991)CrossRefMATH

22.

Huckaby, D.A., Chan, T.F.: Stewart’s pivoted QLP decomposition for low-rank matrices. Numer. Linear Algebra Appl. 12(4), 153–159 (2005)MathSciNetCrossRefMATH

23.

Kahan, W.: Numerical linear algebra. Can. Math. Bull 9, 757–801 (1966)CrossRefMATH

24.

Martinsson, P.G., Quintana, G., Heavner, N., Van de Geijn, R.: Householder qr factorization with randomization for column pivoting (hqrrp). SIAM J. Sci. Comput. 39(2), C96–C115 (2017)MathSciNetCrossRefMATH

25.

Martinsson, P.G., Rokhlin, V., Tygert, M.: A randomized algorithm for the approximation of matrices. Technical Report Yale CS research report YALEU/DCS/RR-1361. Yale University, Computer Science Department (2006)

26.

Mirsky, L.: Symmetric gauge functions and unitarily invariant norms. Q. J. Math. Oxf. Ser. 11(2), 50–59 (1960)MathSciNetCrossRefMATH

27.

O’Rourke, S., Vu, V., Wang, K.: Eigenvectors of random matrices: a survey. J. Comb. Theory Ser. A 144, 361–442 (2016)MathSciNetCrossRefMATH

28.

Pan, C.-T., Tang, P.T.P.: Bounds on singular values revealed by QR factorizations. BIT Numer. Math. 39(4), 740–756 (1999)MathSciNetCrossRefMATH

29.

Rudelson, M.: Invertibility of random matrices: norm of the inverse. Ann. Math. 168, 575–600 (2008)MathSciNetCrossRefMATH

30.

Schneider, P., Eberly, D.H.: Geometric Tools for Computer Graphics. Morgan Kaufmann Publishers Inc., San Francisco, CA (2003)

31.

Stewart, G.W.: The QLP approximation to the singular value decomposition. SIAM J. Sci. Comput. 20(4), 1336–1348 (1999)MathSciNetCrossRefMATH

32.

Szarek, S.J.: Condition numbers of random matrices. J. Complex. 7, 131–149 (1991)MathSciNetCrossRefMATH

33.

Tao, T., Vu, V.: Random matrices: universal properties of eigenvectors. Random Matrices Theory Appl. 1(1), 1150001 (2012)MathSciNetCrossRefMATH

34.

Voronin, S., Martinsson, P.G.: Efficient algorithms for cur and interpolative matrix decompositions. Adv. Comput. Math. 43(3), 495–516 (2017)MathSciNetCrossRefMATH

Titel: ALORA: Affine Low-Rank Approximations
verfasst von: Alan Ayala
Xavier Claeys
Laura Grigori
Publikationsdatum: 28.11.2018
Verlag: Springer US
Erschienen in: Journal of Scientific Computing / Ausgabe 2/2019
Print ISSN: 0885-7474
Elektronische ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-018-0885-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2019

A New Proximal Iterative Hard Thresholding Method with Extrapolation for Minimization

Sensitivity-Driven Adaptive Construction of Reduced-space Surrogates

Physics-Based Balancing Domain Decomposition by Constraints for Multi-Material Problems

Optimized Schwarz Methods for the Optimal Control of Systems Governed by Elliptic Partial Differential Equations

Particle-without-Particle: A Practical Pseudospectral Collocation Method for Linear Partial Differential Equations with Distributional Sources

Local Discontinuous Galerkin Methods for the -Camassa–Holm and -Degasperis–Procesi Equations