Giới hạn trên tối tiểu của sai số cắt của thuật toán xấp xỉ ma trận hạng thấp sử dụng phân rã QR có chốt

Springer Science and Business Media LLC - Tập 38 Số 3 - Trang 757-779 - 2021
Haruka Kawamura1, Reiji Suda1
1The University of Tokyo, Tokyo, Japan

Tóm tắt

Tóm tắtPhân rã QR có chốt (QR phân rã với việc đánh dấu) cho phép xấp xỉ hạng thấp thường có độ chính xác thấp hơn so với phân rã trị riêng (SVD); tuy nhiên, lượng tính toán cần thiết lại ít hơn so với SVD. Giới hạn trên tối thiểu của tỷ lệ sai số cắt, được định nghĩa bởi $$\Vert A-BC\Vert _2$$ A - B C 2 , khi sử dụng QR có chốt so với SVD được chứng minh là $$\sqrt{\frac{4^k-1}{3}(n-k)+1}$$ 4 k - 1 3 ( n - k ) + 1 cho $$A\in {\mathbb {R}}^{m\times n}$$ A R m × n $$(m\ge n)$$ ( m n ) , được xấp xỉ như một sản phẩm của $$B\in {\mathbb {R}}^{m\times k}$$ B R m × k $$C\in {\mathbb {R}}^{k\times n}$$ C R k × n trong nghiên cứu này.

Từ khóa


Tài liệu tham khảo

Björck, Å.: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996)

Businger, P., Golub, G.H.: Linear least squares solutions by householder transformations. Numer. Math. 7, 269–276 (1965)

Chandrasekaran, S., Ipsen, I.C.F.: On rank-revealing factorisations. SIAM J. Matrix Anal. Appl. 15(2), 592–622 (1994)

Drmač, Z., Gugercin, S.: A new selection operator for the discrete empirical interpolation method-improved a priori error bound and extensions. SIAM J. Sci. Comput. 38(2), A631–A648 (2016)

Eldén, L.: Numerical linear algebra in data mining. Acta Numer. 15, 327–384 (2006)

Faddeev, D.K., Kublanovskaya, V.N., Faddeeva, V.N.: Solution of linear algebraic systems with rectangular matrices. Trudy Mat. Inst. Steklov. 96, 76–92 (1968)

Golub, G.H.: Numerical methods for solving linear least squares problems. Numer. Math. 7, 206–216 (1965)

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

Hong, Y.P., Pan, C.-T.: Rank-revealing QR factorizations and the singular value decomposition. Math. Comput. 58, 213–232 (1992)

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

Kawamura, H.: Analysis of truncation error of matrix low rank approximation algorithm using QR decomposition with pivot selection. Trans. Jpn. Soc. Ind. Appl. Math. 30(2), 163–176 (2020)

Khoromskij, B.N.: Tensors-structured numerical methods in scientific computing: survey on recent advances. Chemom. Intell. Lab. Syst. 110, 1–19 (2012)

Kumar, N.K., Schneider, J.: Literature survey on low rank approximation of matrices. Linear Multilinear Algebra 65(11), 2212–2244 (2017)

Ye, J.: Generalized low rank approximations of matrices. Mach. Learn. 61, 167–191 (2005)