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

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