nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Sublinear Cost Low Rank Approximation via Subspace Sampling

verfasst von : Victor Y. Pan, Qi Luan, John Svadlenka, Liang Zhao

Erschienen in: Mathematical Aspects of Computer and Information Sciences

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Low Rank Approximation (LRA) of a matrix is a hot research subject, fundamental for Matrix and Tensor Computations and Big Data Mining and Analysis. Computations with LRA can be performed at sublinear cost, that is, by using much fewer memory cells and arithmetic operations than an input matrix has entries. Although every sublinear cost algorithm for LRA fails to approximate the worst case inputs, we prove that our sublinear cost variations of a popular subspace sampling algorithm output accurate LRA of a large class of inputs.

Namely, they do so with a high probability (whp) for a random input matrix that admits its LRA. In other papers we propose and analyze other sublinear cost algorithms for LRA and Linear Least Sqaures Regression. Our numerical tests are in good accordance with our formal results.

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 "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

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

Vorheriges Kapitel Comprehensive LU Factors of Polynomial Matrices

Nächstes Kapitel CUR LRA at Sublinear Cost Based on Volume Maximization

Nur mit Berechtigung zugänglich

Here and hereafter “Gaussian matrices” stands for “Gaussian random matrices” (see Definition 1). “SRHT and SRFT” are the acronyms for “Subsample Random Hadamard and Fourier transforms”. Rademacher’s are the matrices filled with iid variables, each equal to 1 or \(-1\) with probability 1/2.

Subpermutation matrices are full-rank submatrices of permutation matrices.

\({{\,\mathrm{nrank}\,}}(W)\) denotes numerical rank of W (see Appendix A.1).

We defined Algorithm 4 in Remark 4

Additive white Gaussian noise is statistical noise having a probability density function (PDF) equal to that of the Gaussian (normal) distribution.

[B15]

Björck, Å.: Numerical Methods in Matrix Computations. TAM, vol. 59. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-05089-8CrossRefMATH

[CD05]

Chen, Z., Dongarra, J.J.: Condition numbers of Gaussian random matrices, SIAM. J. Matrix Anal. Appl. 27, 603–620 (2005)MathSciNetCrossRef

[CLO16]

Cichocki, C., Lee, N., Oseledets, I., Phan, A.-H., Zhao, Q., Mandic, D.P.: Tensor networks for dimensionality reduction and large-scale optimization: part 1 low-rank tensor decompositions. Found. Trends® Mach. Learn. 9(4–5), 249–429 (2016)CrossRef

[DS01]

Davidson, K.R., Szarek, S.J.: Local operator theory, random matrices, and banach spaces. In: Johnson, W.B., Lindenstrauss, J., (eds.) Handbook on Geometry of Banach Spaces, pp. 317–368, North Holland (2001)

[E88]

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

[ES05]

Edelman, A., Sutton, B.D.: Tails of condition number distributions. SIAM J. Matrix Anal. Appl. 27(2), 547–560 (2005)MathSciNetCrossRef

[GL13]

Golub, G.H., Van Loan, C.F.: Matrix Computations, fourth edition. The Johns Hopkins University Press, Baltimore (2013)

[GOSTZ10]

Goreinov, S., Oseledets, I., Savostyanov, D., Tyrtyshnikov, E., Zamarashkin, N.: How to find a good submatrix. In: Matrix Methods: Theory, Algorithms, Applications,(dedicated to the Memory of Gene Golub, edited by V. Olshevsky and E. Tyrtyshnikov), pp. 247–256. World Scientific Publishing, New Jersey (2010)

[HMT11]

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)MathSciNetCrossRef

[KS17]

Kishore Kumar, N., Schneider, J.: Literature survey on low rank approximation of matrices. Linear Multilinear Algebra 65(11), 2212–2244 (2017). arXiv:1606.06511v1 [math.NA] 21 June 2016MathSciNetCrossRef

[LPa]

Luan, Q., Pan, V.Y.: CUR LRA at sublinear cost based on volume maximization, In: Salmanig, D. et al. (eds.) MACIS 2019, LNCS 11989, pp. xx–yy. Springer, Switzerland (2020). https://doi.org/10.1007/978-3-030-43120-49. arXiv:1907.10481 (2019)

[LPb]

Luan, Q., Pan, V.Y., Randomized approximation of linear least squares regression at sublinear cost. arXiv:1906.03784, 10 June 2019

[M11]

Mahoney, M.W.: Randomized algorithms for matrices and data. Found. Trends Mach. Learn. 3, 2 (2011)MATH

[O18]

Osinsky, A.: Rectangular maximum volume and projective volume search algorithms. arXiv:1809.02334, September 2018

[P00]

Pan, C.-T.: On the existence and computation of rank-revealing LU factorizations. Linear Algebra Appl. 316, 199–222 (2000)MathSciNetCrossRef

[PLa]

Pan, V.Y., Luan, Q.: Refinement of low rank approximation of a matrix at sublinear cost. arXiv:1906.04223, 10 June 2019

[PLSZ16]

Pan, V.Y., Luan, Q., Svadlenka, J., Zhao, L.: Primitive and Cynical Low Rank Approximation, Preprocessing and Extensions. arXiv 1611.01391, 3 November 2016

[PLSZ17]

Pan, V.Y., Luan, Q., Svadlenka, J., Zhao, L.: Superfast Accurate Low Rank Approximation. Preprint, arXiv:1710.07946, 22 October 2017

[PLSZa]

Pan, V.Y., Luan, Svadlenka, Q., Zhao, L.: CUR Low Rank Approximation at Sublinear Cost. arXiv:1906.04112, 10 June 2019

[PLSZb]

Pan, V.Y., Luan, Q., Svadlenka, J., Zhao, L.: Low rank approximation at sublinear cost by means of subspace sampling. arXiv:1906.04327, 10 June 2019

[PQY15]

Pan, V.Y., Qian, G., Yan, X.: Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation. Linear Algebra Appl. 481, 202–234 (2015)MathSciNetCrossRef

[PZ17a]

Pan, V.Y., Zhao, L.: New studies of randomized augmentation and additive preprocessing. Linear Algebra Appl. 527, 256–305 (2017)MathSciNetCrossRef

[PZ17b]

Pan, V.Y., Zhao, L.: Numerically safe Gaussian elimination with no pivoting. Linear Algebra Appl. 527, 349–383 (2017)MathSciNetCrossRef

[SST06]

Sankar, A., Spielman, D., Teng, S.-H.: Smoothed analysis of the condition numbers and growth factors of matrices. SIMAX 28(2), 446–476 (2006)MathSciNetCrossRef

[T11]

Tropp, J.A.: Improved analysis of subsampled randomized Hadamard transform. Adv. Adapt. Data Anal. 3(1–2), 115–126 (2011). (Special issue "Sparse Representation of Data and Images")MathSciNetCrossRef

[TYUC17]

Tropp, J.A., Yurtsever, A., Udell, M., Cevher, V.: Practical sketching algorithms for low-rank matrix approximation. SIAM J. Matrix Anal. Appl. 38, 1454–1485 (2017)MathSciNetCrossRef

[WLRT08]

Woolfe, F., Liberty, E., Rokhlin, V., Tygert, M.: A fast randomized algorithm for the approximation of matrices. Appl. Comput. Harmonic. Anal. 25, 335–366 (2008)MathSciNetCrossRef

Titel: Sublinear Cost Low Rank Approximation via Subspace Sampling
verfasst von: Victor Y. Pan
Qi Luan
John Svadlenka
Liang Zhao
Verlag: Springer International Publishing
Buch: Mathematical Aspects of Computer and Information Sciences
Print ISBN: 978-3-030-43119-8

Electronic ISBN: 978-3-030-43120-4

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-43120-4_9

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 "Technik"

Springer Professional "Wirtschaft"