Matrix and tensor rigidity and \(L_p\)-approximation

DOI10.1016/j.jco.2022.101651OpenAlexW4213009714WikidataQ114163587 ScholiaQ114163587MaRDI QIDQ2145080

Yuri V. Malykhin

Publication date: 17 June 2022

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov widthslow-rank approximationmatrix rigiditysignum rank

Mathematics Subject Classification ID

Theory of computing (68Qxx) Numerical analysis (65-XX) Approximations and expansions (41Axx) Approximations and expansions (41-XX)

Cites Work

• Probabilistic communication complexity
• Nonlinear tensor product approximation of functions
• Estimates of best bilinear approximations of periodic functions
• Estimates of best bilinear approximations of functions and approximation numbers of integral operators
• Nonlinear methods of approximation
• Kolmogorov width and approximate rank
• Complexity Lower Bounds using Linear Algebra
• Measures of Complexity
• Probabilistic rank and matrix rigidity
• Fourier and circulant matrices are not rigid
• The approximate rank of a matrix and its algorithmic applications
• Lower Bounds for Approximation by Nonlinear Manifolds
• Mathematical analysis II. Transl. from the 4th Russian edition by Roger Cooke
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Matrix and tensor rigidity and \(L_p\)-approximation