On the optimal rank-1 approximation of matrices in the Chebyshev norm

DOI10.1016/J.LAA.2023.09.007MaRDI QIDQ6084872zbMATH OpenFDO

Authors Stanislav Morozov, Matvey Smirnov, N. L. Zamarashkin

Publication date 6 November 2023

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.01438

zbMATH Keywords

alternating minimizationChebyshev normlow-rank matrix approximations

Mathematics Subject Classification ID

Best approximation, Chebyshev systems (41A50) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: The problem of low rank approximation is ubiquitous in science. Traditionally this problem is solved in unitary invariant norms such as Frobenius or spectral norm due to existence of efficient methods for building approximations. However, recent results reveal the potential of low rank approximations in Chebyshev norm, which naturally arises in many applications. In this paper we tackle the problem of building optimal rank-1 approximations in the Chebyshev norm. We investigate the properties of alternating minimization algorithm for building the low rank approximations and demonstrate how to use it to construct optimal rank-1 approximation. As a result we propose an algorithm that is capable of building optimal rank-1 approximations in Chebyshev norm for small matrices.

Recommendations

• On the best approximation algorithm by low-rank matrices in Chebyshev's norm
• Refining uniform approximation algorithm for low-rank Chebyshev embeddings
• On best uniform approximation by low-rank matrices
• The Chebyshev approximation of a rectangular matrix by matrices of smaller rank as the limit of \(\ell_p\)-approximation
• Chebyshev polynomials and best rank-one approximation ratio

Cites work

• Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
• Low-rank matrix approximation in the infinity norm
• Musings on multilinear fitting
• On the best approximation algorithm by low-rank matrices in Chebyshev's norm
• Reducibility among combinatorial problems
• Uniform approximation of a function of two variables, tabulated as the product of functions of a single variable
• Why Are Big Data Matrices Approximately Low Rank?

Cited in

(2)

• On the distance to low-rank matrices in the maximum norm
• Refining uniform approximation algorithm for low-rank Chebyshev embeddings

This page was built for publication: On the optimal rank-1 approximation of matrices in the Chebyshev norm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6084872)