Efficiently computing a matrix's induced p-norm Suppose $A$ is an $m\times n$ real matrix and we need to find $\left\|A\right\|_p$ for $p \notin \{ 1, 2, \infty \}$. What is the most efficient way to compute $\left\|A\right\|_p$? 
Here's one naive approach I can think of. Sample random points $\left\|x\right\|$ on the unit hypersphere  , computing $\left\|Ax\right\|_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.)?
 A: 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.
A: 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.
A: 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).
