Computing the norm ∥A∥∞,1 is NP-hard∗

DOI10.1080/03081080008818644zbMATH Open0964.65049OpenAlexW2032711963MaRDI QIDQ4498326FDOQ4498326

Authors: Jiří Rohn 

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

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

zbMATH Keywords

normNP-hardpolynomial-time algorithmpositive definitenessM-matrix

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Checking robust nonsingularity is NP-hard
• Some simplified NP-complete graph problems
• Algorithmes de calcul du maximum des formes quadratiques sur la boule unité de la norme du max
• Complexity of some linear problems with interval data

Cited In (16)

• Nonsingularity, positive definiteness, and positive invertibility under fixed-point data rounding.
• 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
• On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
• Complexity of necessary efficiency in interval linear programming and multiobjective linear programming
• Bounds for the distance to the nearest correlation matrix
• Linear interval equations: Midpoint preconditioning may produce a 100\% overestimation for arbitrarily narrow data even in case \(n = 4\)
• Complexity issues for the symmetric interval eigenvalue problem
• Error bounds and a condition number for the absolute value equations
• Composite norms and perfect conditioning
• Computational complexity of norm-maximization
• Two proposals for robust PCA using semidefinite programming
• The global convergence of the nonlinear power method for mixed-subordinate matrix norms
• Matrix \(p\)-norms are NP-hard to approximate if \(p\neq1,2,\infty\)
• Optimization of the shape (and topology) of the initial conditions for diffusion parameter identification

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)