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.