# Rectangular maximum-volume submatrices and their applications

@article{Mikhalev2015RectangularMS, title={Rectangular maximum-volume submatrices and their applications}, author={Aleksandr Mikhalev and I. Oseledets}, journal={ArXiv}, year={2015}, volume={abs/1502.07838} }

Abstract We introduce a definition of the volume of a general rectangular matrix, which is equivalent to an absolute value of the determinant for square matrices. We generalize results of square maximum-volume submatrices to the rectangular case, show a connection of the rectangular volume with an optimal experimental design and provide estimates for a growth of coefficients and an approximation error in spectral and Chebyshev norms. Three promising applications of such submatrices are… Expand

#### Figures, Tables, and Topics from this paper

#### 27 Citations

Perturbations of CUR Decompositions

- Computer Science, Mathematics
- SIAM J. Matrix Anal. Appl.
- 2021

P perturbation estimates for several variants of the CUR decomposition are given and illustrate how the choice of columns and rows affects the quality of the approximation, and additionally new state-of-the-art bounds for some variants of CUR approximations are obtained. Expand

Rectangular maximum volume and projective volume search algorithms

- Mathematics
- 2018

New methods for finding submatrices of (locally) maximal volume and large projective volume are proposed and studied. Detailed analysis is also carried out for existing methods. The effectiveness of… Expand

A Note on Error Bounds for Pseudo Skeleton Approximations of Matrices

- Computer Science, Mathematics
- ArXiv
- 2021

Improved bounds for the errors of the matrix elements are provided using the Chebyshev norm, substantially better in the practically relevant cases where the eigenvalues decrease polynomially. Expand

Low-Rank Kernel Matrix Approximation Using Skeletonized Interpolation With Endo- or Exo-Vertices

- Mathematics
- 2018

The efficient compression of kernel matrices, for instance the off-diagonal blocks of discretized integral equations, is a crucial step in many algorithms. In this paper, we study the application of… Expand

Sparse Polynomial Chaos Expansions: Literature Survey and Benchmark

- Computer Science, Mathematics
- SIAM/ASA J. Uncertain. Quantification
- 2021

It is found that the choice of sparse regression solver and sampling scheme for the computation of a sparse PCE surrogate can make a significant difference, of up to several orders of magnitude in the resulting mean-square error. Expand

Function approximation using gradient information with application to parametric and stochastic differential equations

- Mathematics
- 2018

In the paper we consider the problem of multivariate function approximation in polynomial basis. In order to solve this problem, we adjust the least squares method (LSM) by adding information about… Expand

On the Accuracy of Cross and Column Low-Rank Maxvol Approximations in Average

- Mathematics
- Computational Mathematics and Mathematical Physics
- 2021

The article considers the problem of low-rank column and cross (
$$CGR$$
, $$CUR$$
) approximation of matrices in the Frobenius norm up to a fixed factor $$1 + \varepsilon $$
. It is proved that,… Expand

Gradient Descent-based D-optimal Design for the Least-Squares Polynomial Approximation

- Mathematics, Computer Science
- ArXiv
- 2018

High efficiency of the proposed sampling method is demonstrated by its comparison with other sampling techniques (LHS, Sobol' sequence sampling, and Maxvol sampling) on the problem of least-squares polynomial approximation. Expand

Robust CUR Decomposition: Theory and Imaging Applications

- Computer Science, Engineering
- SIAM Journal on Imaging Sciences
- 2021

This paper examines the qualitative behavior of the Robust CUR decompositions on the benchmark videos and face datasets, and finds that the method works as well as standard Robust PCA while being significantly faster. Expand

Co-Separable Nonnegative Matrix Factorization

- Computer Science, Mathematics
- ArXiv
- 2021

This paper generalize separability assumption based on 3-factor NMF M = P1SP2, and require that S is a sub-matrix of the input matrix, and refers to this NMF as a Co-Separable NMF (CoS-NMF). Expand

#### References

SHOWING 1-10 OF 20 REFERENCES

How to find a good submatrix

- Mathematics
- 2010

Pseudoskeleton approximation and some other problems require the knowledge of sufficiently well-conditioned submatrix in a large-scale matrix. The quality of a submatrix can be measured by modulus of… Expand

A Theory of Pseudoskeleton Approximations

- Mathematics
- 1997

Abstract Let an m × n matrix A be approximated by a rank- r matrix with an accuracy e. We prove that it is possible to choose r columns and r rows of A forming a so-called pseudoskeleton component… Expand

A good submatrix is hard to find

- Mathematics, Computer Science
- Oper. Res. Lett.
- 1982

Given a matrix, it is NP-hard to find a 'large' column, row, or arbitraty submatrix that satisfies property @p, where @p is nontrivial, holds for permutation matrices, and is hereditary on… Expand

Subset selection for matrices

- Mathematics
- 1989

Abstract We consider the question of how to delete m − k rows from a matrix X ∈ R m × n so that the resulting matrix A ∈ R k × n is as non-singular as possible. Bounds for the singular values… Expand

Preconditioning of linear least-squares problems by identifying basic variables

- Mathematics
- 2014

The preconditioning of linear least-squares problems is a hard task. The linear model underpinning least-squares problems, that is the overdetermined matrix dening it, does not have the properties of… Expand

TT-cross approximation for multidimensional arrays

- Mathematics
- 2010

Abstract As is well known, a rank- r matrix can be recovered from a cross of r linearly independent columns and rows, and an arbitrary matrix can be interpolated on the cross entries. Other entries… Expand

Preconditioning Linear Least-Squares Problems by Identifying a Basis Matrix

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2015

This work attempts to bypass the ill-conditioning of the linear least-squares problem by finding an nonsingular submatrix of $A$ that reduces the Euclidean norm of $AB^{-1}$. Expand

New accuracy estimates for pseudoskeleton approximations of matrices

- Mathematics
- 2016

A priori accuracy estimates for low-rank approximations using a small number of rows and columns of the initial matrix are proposed. Unlike in the existing methods of pseudoskeleton approximation,… Expand

An algorithm for the construction of “ D -optimal” experimental designs

- Computer Science
- 2000

The algorithm DETMAX is presented, whose purpose is to construct experimental designs that are “D-optimal,” which are designs for which the determinant of X'X is maximum. Expand

The topology of Stiefel manifolds

- Mathematics
- 1976

1. Introduction: algebra versus topology 2. The Stiefel manifolds 3. The auxiliary spaces 4. Retractible fibrations 5. Thom spaces 6. Homotopy equivariance 7. Cross-sections and the S-type 8.… Expand