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



Efficiently computing a matrix's induced p-norm
On the negative side, there is a [result](http://arxiv.org/abs/0908.1397) 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](http://www2.isye.gatech.edu/~nemirovs/Daureen.pdf) has an efficient algorithm for computing the $p$-norm of a nonnegative matrix (see Remark 3.4 on page 48).


