# Efficiently computing a matrix's induced p-norm

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.)?

-
By $\Vert A \Vert_p$, do you mean the norm from $\ell_p$ to $\ell_p$? – Yemon Choi Sep 17 '10 at 22:36

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).

-

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?

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).