Nicholas Higham gives an [algorithm][1] 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?

  [1]: http://dx.doi.org/10.1007/BF01396242