Approximating matrix p-norms
Aditya Bhaskara, Aravindan Vijayaraghavan · Symposium on Discrete Algorithms · 2011
We consider the problem of computing the q ↦ p norm of a matrix A, which is defined for p, q ≥ 1, as[EQUATION]This is in general a non-convex optimization problem, and is a natural generalization of the well-studied question of computing singular values (this corresponds to p = q = 2). Different settings of parameters give rise to a variety of known interesting problems (such as the Grothendieck problem when p = 1 and q = ∞). However, very little is understood about the approximability of the problem for different values of p, q.Our first result is an efficient algorithm for computing the q ↦ p norm of matrices with non-negative entries, when q ≥ p ≥ 1. The algorithm we analyze is based on a natural fixed point iteration, which can be seen as an analog of power iteration for computing eigenvalues.We then present an application of our techniques to the problem of constructing a scheme for oblivious routing in the lp norm. This makes constructive a recent existential result of Englert and Racke [ER09] on O(log n) competitive oblivious routing schemes (which they make constructive only for p = 2).On the other hand, when we do not have any restrictions on the entries (such as non-negativity), we prove that the problem is NP-hard to approximate to any constant factor, for 2 0.