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?

--------

(added 5/13/2011)

I posted a *Mathematica* translation of Higham's [original MATLAB code](http://people.sc.fsu.edu/~jburkardt/m_src/test_matrix/pnorm.m) [here](http://math.stackexchange.com/questions/37913/37939#37939).

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