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

  • $\begingroup$ By $\Vert A \Vert_p$, do you mean the norm from $\ell_p$ to $\ell_p$? $\endgroup$
    – Yemon Choi
    Sep 17 '10 at 22:36

On the negative side, there is a result 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 has an efficient algorithm for computing the $p$-norm of a nonnegative matrix (see Remark 3.4 on page 48).


S.W. Drury derives a method to find the operator norm of a general real matrix $$ A : \ell^p \longrightarrow \ell^q $$ in a recent paper in Lin. Alg. Appl (and using it, refutes a long-standing conjecture of Matsaev).

In keeping with the answer of Alex Olshevsky, the algorithm seems have a complexity exponential in the number of columns of the matrix (but linear in the number of rows).

Drury's implementation for Visual C++ and Maple can be found here, and a C version targeted at Unix and with bindings for Matlab, Octave and Python can be found here.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.