Matrix p-norms are NP-hard to approximate if p1,2,

DOI10.1137/09076773XzbMATH Open1216.68117OpenAlexW1964061391MaRDI QIDQ3079772FDOQ3079772

Authors: Julien M. Hendrickx, Alex Olshevsky 

Publication date: 2 March 2011

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/09076773x

Recommendations

• Computing the norm ∥A∥∞,1 is NP-hard^∗
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• Approximability of \(p\rightarrow q\) matrix norms: generalized Krivine rounding and hypercontractive hardness
• scientific article; zbMATH DE number 6783411
• Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms

zbMATH Keywords

complexityNP-hardnessmatrix norms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Cited In (62)

• Alternated inertial algorithms for split feasibility problems
• A new self-adaptive method for the multiple-sets split common null point problem in Banach spaces
• On the tensor spectral \(\mathbf{p}\)-norm and its higher order power method
• Strongly convergent inertial projection and contraction methods for split variational inequality problem
• Rigorous data‐driven computation of spectral properties of Koopman operators for dynamical systems
• Multiplier algebras of \(L^p\)-operator algebras
• A novel low-cost method for generalized split inverse problem of finite family of demimetric mappings
• Dual Variable Inertial Accelerated Algorithm for Split System of Null Point Equality Problems
• New inertial method for generalized split variational inclusion problems
• An iterative algorithm with inertial technique for solving the split common null point problem in Banach spaces
• Parallel proximal method of solving split system of fixed point set constraint minimization problems
• Relaxed inertial methods for solving split variational inequality problems without product space formulation
• A viscosity iterative technique for split variational inclusion and fixed point problems between a Hilbert space and a Banach space
• Convergence analysis for solving equilibrium problems and split feasibility problems in Hilbert spaces
• A self-adaptive projection method with an inertial technique for split feasibility problems in Banach spaces with applications to image restoration problems
• A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps
• Estimating the matrix \(p\)-norm
• Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors
• Estimating \(L^\infty\) norms by \(L^{2k}\) norms for functions on orbits.
• Moments tensors, Hilbert's identity, and \(k\)-wise uncorrelated random variables
• Title not available (Why is that?)
• New inertial relaxed method for solving split feasibilities
• Tensor norm and maximal singular vectors of nonnegative tensors -- a Perron-Frobenius theorem, a Collatz-Wielandt characterization and a generalized power method
• Inertial accelerated steepest descent algorithm for generalized split common fixed point problems
• A survey of hidden convex optimization
• Dynamical technique for split common fixed point problem in Banach spaces
• Image restorations using a modified relaxed inertial technique for generalized split feasibility problems
• Halpern-type iterative process for solving split common fixed point and monotone variational inclusion problem between Banach spaces
• Tight computationally efficient approximation of matrix norms with applications
• Error bounds and a condition number for the absolute value equations
• An inertial self-adaptive algorithm for the generalized split common null point problem in Hilbert spaces
• A new self-adaptive accelerated method for generalized split system of common fixed-point problem of averaged mappings
• A new method for solving split variational inequality problems without co-coerciveness
• On split generalised mixed equilibrium problems and fixed-point problems with no prior knowledge of operator norm
• Viscosity self-adaptive method for generalized split system of variational inclusion problem
• The global convergence of the nonlinear power method for mixed-subordinate matrix norms
• An iterative method for split inclusion problems without prior knowledge of operator norms
• Proximal method of solving split system of minimization problem
• Inertial-viscosity-type algorithms for solving generalized equilibrium and fixed point problems in Hilbert spaces
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Pseudoergodic operators and periodic boundary conditions
• Inertial methods for finding minimum-norm solutions of the split variational inequality problem beyond monotonicity
• A simple strong convergent method for solving split common fixed point problems
• Computing the norm ∥A∥∞,1 is NP-hard^∗
• Nuclear norm of higher-order tensors
• A new viscosity-type iteration for a finite family of split variational inclusion and fixed point problems between Hilbert and Banach spaces
• An inertial extrapolation method for multiple-set split feasibility problem
• Weak and strong convergence adaptive algorithms for generalized split common fixed point problems
• Convergence analysis of an inertial accelerated iterative algorithm for solving split variational inequality problem
• Polynomial norms
• Approximability of \(p\rightarrow q\) matrix norms: generalized Krivine rounding and hypercontractive hardness
• A note on the Hausdorff distance between norm balls and their linear maps
• A modified contraction method for solving certain class of split monotone variational inclusion problems with application
• Global and linear convergence of alternated inertial methods for split feasibility problems
• An inertial method for solving generalized split feasibility problems over the solution set of monotone variational inclusions
• Iterative methods for the split feasibility problem and the fixed point problem in Banach spaces
• Stability analysis of linear delay systems via internally positive representations: an overview
• A unified algorithm for solving split generalized mixed equilibrium problem, and for finding fixed point of nonspreading mapping in Hilbert spaces
• Title not available (Why is that?)
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
• Convergence analysis for the proximal split feasibility problem using an inertial extrapolation term method
• On low rank approximation of linear operators in \(p\)-norms and some algorithms

This page was built for publication: Matrix \(p\)-norms are NP-hard to approximate if \(p\neq1,2,\infty\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3079772)