The maximum-volume concept in approximation by low-rank matrices

By Sergei A. Goreinov, E. E. Tyrtyshnikov. 2001

215 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/3ca6f4d92d1ea57c5f52170a85d63da1f1355a81

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

Citations in the corpus

TT-cross approximation for multidimensional arrays (2010, methodology): “In that case an answer is to use the intersection submatrix with maximal volume (i.e. determinant in modulus) [24].”
Wedderburn Rank Reduction and Krylov Subspace Method for Tensor Approximation. Part 1: Tucker Case (2010, methodology): “Cross methods compute rank-r approximation by interpolating the n1 × n2 matrix on a cleverly chosen set of crosses, proposed for instance in [36, 15].”
Randomized Matrix Computations (2012, unknown): “Its previous study can be largely traced through the papers [GTZ97], [GT01], [GOS08], [T00], [MMD08], [OT09], [HMT11], and the bibliography therein, but much earlier advances in this area appeared in the papers [BCLR79], [B80], [B85], [B86], [BC87], directed to estimating the border rank of matrices”
On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning (2005, background): “Examples may be found in [17], and also in [25, 24].”
Relative-Error CUR Matrix Decompositions (2007, background): “Goreinov, Tyrtyshnikov, and Zamarashkin [39, 38, 61] were interested in applications such as scattering, in which large coeﬃcient matrices have blocks that can be easily approximated by low-rank matrices.”
On selecting a maximum volume sub-matrix of a matrix and related problems (2009, unknown): “Goreinov and Tyrtyshnikov [13] provide a more explicit statement of how volume is related to low-rank approximations in the following theorem: Theorem 1 ([13] ).”
Linear algebra for tensor problems (2009, background): “[10,11] for the 2D case) and developed in [7,9] making a Tucker approximation feasible even for huge-scale tensors.”
Efficient Volume Sampling for Row/Column Subset Selection (2010, methodology): “A recent article by Mahoney and Drineas [18] highlights the limitations of PCA and gives experimental data on practical applications of low-rank approximation based on row/column-subset selection.”
How to find a good submatrix (2010, background): “A theoretical answer (basically, existence theory) [3] is that if Â has maximal in modulus determinant among all r × r submatrices of A, then element-wise error estimate is of the form |A − Ar| ≤ (r + 1)σr+1, 1”
Fast truncation of mode ranks for bilinear tensor operations (2010, background): “In [17, 18, 16] it is shown that a good choice for A[I, J] is maximum volume (modulus of determinant) submatrix.”
Tensor properties of multilevel Toeplitz and related matrices (2006, background): “Moreover, accurate low-rank approximation can be often obtained from picking up only a relatively small number of entries, which leads to very efficient practical algorithms (cf [8,9,28]).”
CUR matrix decompositions for improved data analysis (2009, background): “, such as to define a parallelepiped of maximal volume over all (n k ) such parallelepipeds, or to span a subspace that “captures” a maximal amount of variance from A over all (n k ) such subspaces—most such criteria would lead to intractable combinatorial optimization problems (9, 10, 18).”
Verification of the cross 3D algorithm on quantum chemistry data (2008, background): “This maximal volume submatrix excels in a good accuracy bound to hold [22].”
Superfast Fourier Transform Using QTT Approximation (2012, background): “They are based on the maximum-volume principle [11, 13], which selects proper sets of indices in the array for the interpolation procedure.”
Fast adaptive interpolation of multi-dimensional arrays in tensor train format (2011, background): “The maximum volume principle [19] states, that the submatrix with maximal volume, i.”
Cross approximation in tensor electron density computations (2010, methodology): “Although it cannot be so in all cases, in many practical applications we find that the accuracy of Algorithm 3 is reasonably close to that of the SVD truncation [6, 15, 24].”
Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time (2008, background): “In the works [13, 14, 18] the problem of finding a rank-r approximation to a given matrix was connected with finding in matrix A a submatrix of maximal volume (i.”