Incomplete Cross Approximation in the Mosaic-Skeleton Method

By E. E. Tyrtyshnikov. 2000

275 citations recorded by the source corpus.

Subfields: Atomic and Molecular Physics, and Optics, Computational Theory and Mathematics, Statistical and Nonlinear Physics

How researchers see this paper

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

In Atomic and Molecular Physics, and Optics

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “For an m × n matrix A , the so called cross approximation method [19, 34, 100, 248] produces an approximation of the form A (: , J ) A ( I, J ) − 1 A ( I,”
Fast truncation of mode ranks for bilinear tensor operations (2010, background): “Search of this submatrix in general case is NP-hard problem [1], and alternatives should be used, see [29, 13].”
Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions (2009, unknown): “, cross-approximation algorithm [16]).”
TT-cross approximation for multidimensional arrays (2010, methodology): “However, in the work with tensor trains we need some additional properties for the skeleton decomposition in two dimensions and find it most useful to fall back to constructions of the cross approximation method proposed in [39].”
Cross approximation in tensor electron density computations (2010, methodology): “2010; 17:935–952 DOI: 10.1002/nla Algorithm 3 Savostyanov [6] and Tyrtyshnikov [14] Cross2D matrix approximation Input: Matrix F”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “For example, [118, 119, 55, 54] discuss the so-called skeleton approximation, which focuses on the spectral norm version of the CUR problem via selecting exactly k columns and k rows.”
A fast 3D dual boundary element method based on hierarchical matrices (2008, methodology): “This idea paved the way to the development of purely algebraic techniques for the approximation of large BEM matrices, like the mosaic-skeleton method ( Tyrtyshnikov, 1996, 2000; Goreinov et al., 1997).”
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.”
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].”
Tensor approximations of matrices generated by asymptotically smooth functions (2003, methodology): “Methods of approximation using only the entries of the original matrix are developed in [12]–[16].”
Tensor properties of multilevel Toeplitz and related matrices (2006, methodology): “Computation of Yi reduces to a lower-rank approximation to a given lowrank matrix; this can be done efficiently by the SVD-based procedure called recompression [10,28].”
Efficient High-Dimensional Stochastic Optimal Motion Control using Tensor-Train Decomposition (2015, background): “Recall that the skeleton decomposition [25] of an m× n rank r matrix A can written as A = A[:, C]A[I, C]†A[C, :], where I is a set of rows with |I| ≥ r and C is a set of columns with |C| ≥ r.”