Computing the norm ∥A∥∞,1 is NP-hard∗
From MaRDI portal
Publication:4498326
Recommendations
- Matrix p-norms are NP-hard to approximate if p1,2,
- 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 Overell_inftyNorm
Cites work
- 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
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Some simplified NP-complete graph problems
Cited in
(21)- Complexity of necessary efficiency in interval linear programming and multiobjective linear programming
- Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard
- Two proposals for robust PCA using semidefinite programming
- The global convergence of the nonlinear power method for mixed-subordinate matrix norms
- Optimization of the shape (and topology) of the initial conditions for diffusion parameter identification
- Complexity of computing interval matrix powers for special classes of matrices.
- Maximization of a PSD quadratic form and factorization
- 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\)
- Error bounds and a condition number for the absolute value equations
- Bounds for the distance to the nearest correlation matrix
- Matrix p-norms are NP-hard to approximate if p1,2,
- Composite norms and perfect conditioning
- Tolerances, robustness and parametrization of matrix properties related to optimization problems
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Exact calculation of some induced matrix norms
- Estimating the matrix p q norm
- Global sensitivity analysis and robustness in linear programming using different norms
- Tolerance analysis in linear programming: searching for lower and upper bounds
- Computational complexity of norm-maximization
- Nonsingularity, positive definiteness, and positive invertibility under fixed-point data rounding.
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)
