Matrix P-norms are NP-hard to approximate if p \neq 1,2,\infty

Julien M. Hendrickx, Alexander Olshevsky

TL;DR

This paper proves that for most values of p, approximating the matrix p-norm is computationally intractable (NP-hard), meaning no efficient algorithm likely exists. This is a significant result because matrix norms are fundamental in many areas of mathematics and computer science, and this work establishes a strong theoretical barrier to their efficient computation.

What Problem Does This Paper Address?

Matrix norms are fundamental quantities that measure the "size" or "magnitude" of a matrix. The p-norm, in particular, is a generalization of familiar norms like the Frobenius norm and the spectral norm (2-norm). While the 1-norm, 2-norm, and infinity-norm of a matrix can be computed efficiently, the p-norm for other values of p (especially p > 2) has been suspected to be computationally difficult. This paper tackles the question of whether there exist efficient (polynomial-time) algorithms to approximate these p-norms to a desired level of accuracy. The authors also investigate the related problem of approximating mixed matrix norms, which combine different p-norms.

Methods

The core of the paper's argument relies on a reduction from the well-known NP-hard problem of "maximum cut" in graph theory to the problem of approximating matrix p-norms.

  1. Max-Cut to Mixed Norm Reduction: The authors first show that approximating the mixed norm $||A||_{\infty,p}$ is NP-hard. They construct a specific matrix $M(G)$ related to a graph $G$. They prove that the $\infty,p$-norm of $M(G)$ is directly related to the maximum cut of $G$. This allows them to show that if one could efficiently approximate the $\infty,p$-norm, they could efficiently solve the max-cut problem, which is known to be hard.
  2. Mixed Norm to p-Norm Reduction: The crucial step is then to connect the hardness of approximating the mixed norm to the hardness of approximating the p-norm itself. They construct a larger matrix $Z$ by combining the matrix $M(G)$ (from the first step) and another specially designed matrix $A$. This matrix $A$ is constructed such that its p-norm is maximized at specific "extreme" vectors (those with entries only $\pm 1$). By carefully choosing the scaling of $M(G)$ and $A$ within $Z$, they ensure that the p-norm of $Z$ is dominated by the p-norm of $A$ when evaluated at these extreme vectors. They then show that approximating the p-norm of $Z$ to a certain relative accuracy is equivalent to approximating the maximum cut of the original graph $G$.

Datasets

Not discussed in the paper. The paper focuses on theoretical hardness results and constructs matrices based on graph structures rather than using pre-existing datasets.

Key Insights and Ideas

  • The "Diagonal" Case is Hard: The paper establishes that for p values other than 1, 2, and $\infty$, approximating the matrix p-norm is computationally hard. This is a significant theoretical result, as it implies that for most p, we shouldn't expect to find efficient algorithms for this task.
  • Max-Cut as a Universal Hardness Source: The paper masterfully uses the max-cut problem as a reduction tool. By showing that approximating matrix norms can be reduced from max-cut, they leverage the known hardness of max-cut to prove the hardness of norm computation.
  • Constructing "Extreme" Optimizers: A key technical innovation is the construction of matrices (like $A$) where the p-norm is achieved precisely at vectors with entries $\pm 1$. This property is crucial for linking the norm computation to graph problems.
  • Bridging Mixed Norms and p-Norms: The paper elegantly connects the hardness of approximating mixed norms ($||\cdot||_{\infty,p}$) to the hardness of approximating the standard p-norm ($||\cdot||_p$) by constructing a composite matrix $Z$.

Key Results

  • NP-Hardness for p-Norm Approximation: For any rational $p \in [1, \infty)$ except $p=1, 2, \infty$, approximating the matrix p-norm to arbitrary relative precision is NP-hard. This means no polynomial-time algorithm is likely to exist unless P=NP.
  • NP-Hardness for Mixed Norm Approximation: For any rational $p \in [1, \infty)$, approximating the mixed norm $||A||_{\infty,p}$ to a fixed relative precision is NP-hard.
  • Matrices with $\pm 1$ Entries: The paper shows that computing the p-norm for matrices with entries restricted to $\{-1, 0, 1\}$ is also NP-hard for $p \neq 1, 2, \infty$.

Limitations and Future Work

  • Rational p: The results are primarily stated for rational values of p. Extending these results to irrational p might be an interesting direction.
  • Fixed Relative Error: For the mixed norm, the NP-hardness is shown for a fixed relative error, which depends on p. The paper also shows NP-hardness for the p-norm with a relative error that depends on n (the dimension of the matrix). It would be interesting to see if tighter bounds on the error can be achieved for the p-norm while maintaining NP-hardness.
  • Economical Reductions: The authors mention that their reductions might not be the most "economical" and that more efficient reductions (scaling better with n and p) might exist.
  • Open Cases for Mixed Norms: The paper notes that the case of mixed norms $||A||_{p,q}$ where $p > q$ is still open for certain combinations, although they provide a new proof for some cases.

Summary updated

Abstract

We show that for any rational p \in [1,\infty) except p = 1, 2, unless P = NP, there is no polynomial-time algorithm for approximating the matrix p-norm to arbitrary relative precision. We also show that for any rational p\in [1,\infty) including p = 1, 2, unless P = NP, there is no polynomial-time algorithm approximates the \infty, p mixed norm to some fixed relative precision.
BibTeX
@article{hendrickx2010matrix,
  author = {Julien M. Hendrickx and Alexander Olshevsky},
  title = {{Matrix P-norms are NP-hard to approximate if p \textbackslash\{\}neq 1,2,\textbackslash\{\}infty}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2010},
  url = {https://openreview.net/forum?id=Ir4safCbdt},
}

Loading related content...

Figure