×

A theory of pseudoskeleton approximations. (English) Zbl 0877.65021

From the authors’ abstract: Let an \(m\times n\) matrix \(A\) be approximated by a rank-\(r\) matrix with an accuracy \(\varepsilon\). The paper presents a proof that it is possible to choose \(r\) columns and \(r\) rows of \(A\) forming a so-called pseudoskeleton component which approximates \(A\) with \({\mathcal O}(\varepsilon\sqrt r(\sqrt m+\sqrt n))\) accuracy in the sense of the 2-norm. On the way to this estimate a study concerning the interconnection between the volume (i.e., the determinant in the absolute value) and the minimal singular value \(\sigma_r\) of \(r\times r\) submatrices of an \(n\times r\) matrix with orthogonal columns is presented. Furthermore, the authors propose a lower bound for the maximum of \(\sigma_r\) over all these submatrices and formulate a hypothesis on a tighter bound.

MSC:

65F30 Other matrix algorithms (MSC2010)
Full Text: DOI

References:

[1] Chandrasekaran, S.; Ipsen, I., On Rank-Revealing QR Factorizations, (Res. Rep. YALEU/DCS/RR-880 (1991), Yale University)
[2] Golub, G.; Van Loan, C. F., Matrix Computations (1989), Johns Hopkins UP: Johns Hopkins UP Berkeley · Zbl 0733.65016
[3] Hong, Y. P.; Pan, C.-T., Rank-revealing QR factorizations and singular value decomposition, Math. Comp., 58, 197, 213-232 (1992) · Zbl 0743.65037
[4] Goreinov, S. A.; Tytyshinikov, E. E.; Zamarashkin, N. L., Pseudo-skeleton approximations of matrices, Rep. Russ. Acad. Sci., 343, 2, 151-152 (1995) · Zbl 0875.15004
[5] Rao, S. M.; Wilton, D. R.; Glisson, A. W., Electromagnetic scattering by surfaces of arbitrary shape, IEEE Trans. Antennas Propagat., AP-30, 409-418 (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.