Computing the norm ∥A∥∞,1 is NP-hard∗
From MaRDI portal
Publication:4498326
DOI10.1080/03081080008818644zbMath0964.65049OpenAlexW2032711963MaRDI QIDQ4498326
Publication date: 26 June 2001
Published in: Linear and Multilinear Algebra (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/03081080008818644
Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Complexity and performance of numerical algorithms (65Y20)
Related Items (14)
Error bounds and a condition number for the absolute value equations ⋮ Optimization of the shape (and topology) of the initial conditions for diffusion parameter identification ⋮ Composite norms and perfect conditioning ⋮ Two proposals for robust PCA using semidefinite programming ⋮ Complexity of computing interval matrix powers for special classes of matrices. ⋮ Tolerances, robustness and parametrization of matrix properties related to optimization problems ⋮ Maximization of a PSD quadratic form and factorization ⋮ Nonsingularity, positive definiteness, and positive invertibility under fixed-point data rounding. ⋮ Complexity of necessary efficiency in interval linear programming and multiobjective linear programming ⋮ Complexity issues for the symmetric interval eigenvalue problem ⋮ Linear interval equations: Midpoint preconditioning may produce a 100\% overestimation for arbitrarily narrow data even in case \(n = 4\) ⋮ The global convergence of the nonlinear power method for mixed-subordinate matrix norms ⋮ On the Complexity of Robust PCA and ℓ1-Norm Low-Rank Matrix Approximation ⋮ Bounds for the Distance to the Nearest Correlation Matrix
Cites Work
This page was built for publication: Computing the norm ∥A∥∞,1 is NP-hard∗
