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

DOI10.1016/J.LAA.2023.09.007zbMATH Open1528.65026arXiv2212.01438MaRDI QIDQ6084872FDOQ6084872

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)

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.

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

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

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)

Cites Work

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

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)