We introduce a definition of the volume for a general rectangular matrix, which for square matrices is equivalent to the absolute value of the determinant. We generalize results for square maximum-volume submatrices to the case of rectangular maximal
-volume submatrices, show connection of the rectangular volume with optimal experimental design and provide estimates for the growth of the coefficients and approximation error in spectral and Chebyshev norms. Three promising applications of such submatrices are presented: recommender systems, finding maximal elements in low-rank matrices and preconditioning of overdetermined linear systems. The code is available online.
We propose a new method for the approximate solution of the Lyapunov equation with rank-$1$ right-hand side, which is based on extended rational Krylov subspace approximation with adaptively computed shifts. The shift selection is obtained from the c
onnection between the Lyapunov equation, solution of systems of linear ODEs and alternating least squares method for low-rank approximation. The numerical experiments confirm the effectiveness of our approach.
We propose a new cross-conv algorithm for approximate computation of convolution in different low-rank tensor formats (tensor train, Tucker, Hierarchical Tucker). It has better complexity with respect to the tensor rank than previous approaches. The
new algorithm has a high potential impact in different applications. The key idea is based on applying cross approximation in the frequency domain, where convolution becomes a simple elementwise product. We illustrate efficiency of our algorithm by computing the three-dimensional Newton potential and by presenting preliminary results for solution of the Hartree-Fock equation on tensor-product grids.
A new fast algebraic method for obtaining an $mathcal{H}^2$-approximation of a matrix from its entries is presented. The main idea behind the method is based on the nested representation and the maximum-volume principle to select submatrices in low-r
ank matrices. A special iterative approach for the computation of so-called representing sets is established. The main advantage of the method is that it uses only the hierarchical partitioning of the matrix and does not require special proxy surfaces to be selected in advance. The numerical experiments for the electrostatic problem and for the boundary integral operator confirm the effectiveness and robustness of the approach. The complexity is linear in the matrix size and polynomial in the ranks. The algorithm is implemented as an open-source Python package that is available online.
New algorithms are proposed for the Tucker approximation of a 3-tensor, that access it using only the tensor-by-vector-by-vector multiplication subroutine. In the matrix case, Krylov methods are methods of choice to approximate the dominant column an
d row subspaces of a sparse or structured matrix given through the matrix-by-vector multiplication subroutine. Using the Wedderburn rank reduction formula, we propose an algorithm of matrix approximation that computes Krylov subspaces and allows generalization to the tensor case. Several variants of proposed tensor algorithms differ by pivoting strategies, overall cost and quality of approximation. By convincing numerical experiments we show that the proposed methods are faster and more accurate than the minimal Krylov recursion, proposed recently by Elden and Savas.
