Matrix p-Norms Are NP-Hard to Approximate If $p\neq1,2,\infty$
From MaRDI portal
Publication:3079772
DOI10.1137/09076773XzbMath1216.68117OpenAlexW1964061391MaRDI QIDQ3079772
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
Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A viscosity iterative technique for split variational inclusion and fixed point problems between a Hilbert space and a Banach space ⋮ Tensor norm and maximal singular vectors of nonnegative tensors -- a Perron-Frobenius theorem, a Collatz-Wielandt characterization and a generalized power method ⋮ Dynamical technique for split common fixed point problem in Banach spaces ⋮ Stability Analysis of Linear Delay Systems via Internally Positive Representations: An Overview ⋮ Weak and strong convergence adaptive algorithms for generalized split common fixed point problems ⋮ 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 ⋮ An inertial method for solving generalized split feasibility problems over the solution set of monotone variational inclusions ⋮ Relaxed inertial methods for solving split variational inequality problems without product space formulation ⋮ An iterative algorithm with inertial technique for solving the split common null point problem in Banach spaces ⋮ A new method for solving split variational inequality problems without co-coerciveness ⋮ Halpern-type iterative process for solving split common fixed point and monotone variational inclusion problem between Banach spaces ⋮ A survey of hidden convex optimization ⋮ New inertial method for generalized split variational inclusion problems ⋮ Convergence analysis for the proximal split feasibility problem using an inertial extrapolation term method ⋮ Nonlinear Perron--Frobenius Theorems for Nonnegative Tensors ⋮ A note on the Hausdorff distance between norm balls and their linear maps ⋮ An iterative method for split inclusion problems without prior knowledge of operator norms ⋮ On split generalised mixed equilibrium problems and fixed-point problems with no prior knowledge of operator norm ⋮ A modified contraction method for solving certain class of split monotone variational inclusion problems with application ⋮ Inertial accelerated steepest descent algorithm for generalized split common fixed point problems ⋮ Convergence analysis for solving equilibrium problems and split feasibility problems in Hilbert spaces ⋮ Alternated inertial algorithms for split feasibility problems ⋮ A new self-adaptive method for the multiple-sets split common null point problem in Banach spaces ⋮ Error bounds and a condition number for the absolute value equations ⋮ Rigorous data‐driven computation of spectral properties of Koopman operators for dynamical systems ⋮ Image restorations using a modified relaxed inertial technique for generalized split feasibility problems ⋮ Nuclear norm of higher-order tensors ⋮ Unnamed Item ⋮ Iterative methods for the split feasibility problem and the fixed point problem in Banach spaces ⋮ Global and linear convergence of alternated inertial methods for split feasibility problems ⋮ Inertial methods for finding minimum-norm solutions of the split variational inequality problem beyond monotonicity ⋮ A novel low-cost method for generalized split inverse problem of finite family of demimetric mappings ⋮ A self-adaptive projection method with an inertial technique for split feasibility problems in Banach spaces with applications to image restoration problems ⋮ Convergence analysis of an inertial accelerated iterative algorithm for solving split variational inequality problem ⋮ Unnamed Item ⋮ A unified algorithm for solving split generalized mixed equilibrium problem, and for finding fixed point of nonspreading mapping in Hilbert spaces ⋮ Pseudoergodic operators and periodic boundary conditions ⋮ Parallel proximal method of solving split system of fixed point set constraint minimization problems ⋮ Viscosity self-adaptive method for generalized split system of variational inclusion problem ⋮ New inertial relaxed method for solving split feasibilities ⋮ The global convergence of the nonlinear power method for mixed-subordinate matrix 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 ⋮ On Low Rank Approximation of Linear Operators in p-Norms and Some Algorithms ⋮ 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 ⋮ A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps ⋮ Moments Tensors, Hilbert's Identity, and k-wise Uncorrelated Random Variables ⋮ Grothendieck constant is norm of Strassen matrix multiplication tensor ⋮ Dual Variable Inertial Accelerated Algorithm for Split System of Null Point Equality Problems
