How to find a good submatrix

By Sergei A. Goreinov, Ivan V. Oseledets, Dmitry V. Savostyanov, E. E. Tyrtyshnikov, Nickolai L. Zamarashkin. 2010

298 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Theory and Mathematics, Numerical Methods & Scientific Computing, Algorithms & Complexity

How researchers see this paper

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

In Artificial Intelligence

In Computational Mathematics

In Computational Theory and Mathematics

In Numerical Methods & Scientific Computing

In Algorithms & Complexity

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Volume maximization is an alternative entry selection strategy that attempts to maximize ∣∣det (A(I, J))∣∣, see [100, 250].”
Fast truncation of mode ranks for bilinear tensor operations (2010, unknown): “Search of this submatrix in general case is NP-hard problem [1], and alternatives should be used, see [29, 13].”
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”
Active learning of linearly parametrized interatomic potentials (2016, methodology): “We have proposed a new active learning scheme based on the D-optimality criterion and have shown empirically that it yields an accurate, computationally e ﬃ cient, and reliable in-teratomic interaction model.”
Cross approximation in tensor electron density computations (2010, methodology): “a canonical factor), with a guaranteed approximation accuracy if the intersection matrix is picked up close to a maximum volume submatrix [15, 25], and can be computed via cross approximation procedures [6, 14].”
Wedderburn Rank Reduction and Krylov Subspace Method for Tensor Approximation. Part 1: Tucker Case (2010, methodology): “We can also be satisfied with the sub-optimal but fast formula for G, for example the one based on interpolation on a maximum-volume set of indices [14] as proposed in [26].”
TT-cross approximation for multidimensional arrays (2010, methodology): “Then a quasi-maximal volume submatrix Â in C can be found in O(nr(2)) operations [39] (for more details of the algorithm, called maxvol algorithm, and some roundabout matters see [21]).”
Superfast Fourier Transform Using QTT Approximation (2012, background): “They are based on the maximum–volume principle [15, 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, methodology): “Such algorithm (maxvol) was provided in [20], is fast and robust.”
The MLIP package: moment tensor potentials with MPI and active learning (2020, methodology): “A practical way to construct an active set from a pool of configuration is provided by the Maxvol algorithm for finding the submatrix of maximal volume in a tall matrix [23].”
Quantics-TT Collocation Approximation of Parameter-Dependent and Stochastic Elliptic PDEs (2010, methodology): “For the residue tensor, v(x, y) = f − Au, x ∈ R , y ∈ ΓM , we can find an approximate maximal element, where the residual is small, using multidimensional generalization of the maxvol algorithm [8].”