Efficiently computing a matrix's induced p-norm - MathOverflow

Efficiently computing a matrix's induced p-norm

2010-09-17T21:13:17Z

Suppose $A$ is an $m\times n$ real matrix and we need to find $||A||_p$ for $p \notin {1,2,\infty }$. What is the most efficient way to compute $||A_p||$?

Here's one naive approach I can think of. Sample random points ||x|| on the unit hypersphere , computing $||Ax||_p$ for each such and take the maximum. What I would like to know is the runtime of this approach for the "average" A,and how we can optimize this for special classes of matrices( like Diagonal, Orthonormal, etc.)?

Answer by alex o. for Efficiently computing a matrix's induced p-norm

2010-09-17T21:45:05Z

On the negative side, there is a result by myself and Julien Hendrickx that the matrix $p$-norm is NP-hard to approximate whenever $p$ is not $1,2,$ or $\infty$.

On the positive side, the M.S. thesis of Daureen Steinberg has an efficient algorithm for computing the $p$-norm of a nonnegative matrix (see Remark 3.4 on page 48).

Answer by J. M. for Efficiently computing a matrix's induced p-norm

2010-09-18T01:06:18Z

Nicholas Higham gives an algorithm for estimating the Hölder $p$-norm of a matrix with the estimate being within a factor of $n^{1-1/p} \|\mathbf{A}\|_p$ ; maybe you can somehow adapt this approach to your needs?

(added 5/13/2011)

I posted a Mathematica translation of Higham's original MATLAB code here.

Answer by J.J. Green for Efficiently computing a matrix's induced p-norm

2011-07-15T16:27:00Z

S.W. Drury derives a method to find the operator norm of a general real matrix $$ A : \ell^p \longrightarrow \ell^q $$ in a recent paper in Lin. Alg. Appl (and using it, refutes a long-standing conjecture of Matsaev).

In keeping with the answer of Alex Olshevsky, the algorithm seems have a complexity exponential in the number of columns of the matrix (but linear in the number of rows).

Drury's implementation for Visual C++ and Maple can be found here, and a C version targeted at Unix and with bindings for Matlab, Octave and Python can be found here.