Computing the norm ∥A∥∞,1 is NP-hard∗
From MaRDI portal
Publication:4498326
Recommendations
- Matrix \(p\)-norms are NP-hard to approximate if \(p\neq1,2,\infty\)
- On computing the infinity norm
- On the complexity of computing the \(L_q\) norm
- An Efficient Algorithm for Computing the ${\cal H}_{\infty}$ Norm
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Computational complexity of norm-maximization
- Computation of infimalH∞ norm over a finite horizon
- scientific article; zbMATH DE number 1507221
- Computing \(p\)-summing norms with few vectors
- The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Algorithmes de calcul du maximum des formes quadratiques sur la boule unité de la norme du max
- Checking robust nonsingularity is NP-hard
- Complexity of some linear problems with interval data
- Some simplified NP-complete graph problems
Cited in
(16)- Matrix \(p\)-norms are NP-hard to approximate if \(p\neq1,2,\infty\)
- Complexity issues for the symmetric interval eigenvalue problem
- Nonsingularity, positive definiteness, and positive invertibility under fixed-point data rounding.
- The global convergence of the nonlinear power method for mixed-subordinate matrix norms
- Error bounds and a condition number for the absolute value equations
- Two proposals for robust PCA using semidefinite programming
- Optimization of the shape (and topology) of the initial conditions for diffusion parameter identification
- Maximization of a PSD quadratic form and factorization
- Tolerances, robustness and parametrization of matrix properties related to optimization problems
- Bounds for the distance to the nearest correlation matrix
- Composite norms and perfect conditioning
- Complexity of necessary efficiency in interval linear programming and multiobjective linear programming
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Computational complexity of norm-maximization
- Linear interval equations: Midpoint preconditioning may produce a 100\% overestimation for arbitrarily narrow data even in case \(n = 4\)
- Complexity of computing interval matrix powers for special classes of matrices.
This page was built for publication: Computing the norm ∥A∥∞,1 is NP-hard∗
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4498326)
