Efficiently computing a matrix's induced p-norm - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T16:50:48Z http://mathoverflow.net/feeds/question/39148 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39148/efficiently-computing-a-matrixs-induced-p-norm Efficiently computing a matrix's induced p-norm Ganesh 2010-09-17T21:13:17Z 2011-07-15T16:27:00Z <p>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||$? </p> <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.)?</p> http://mathoverflow.net/questions/39148/efficiently-computing-a-matrixs-induced-p-norm/39151#39151 Answer by alex o. for Efficiently computing a matrix's induced p-norm alex o. 2010-09-17T21:45:05Z 2010-09-17T21:45:05Z <p>On the negative side, there is a <a href="http://arxiv.org/abs/0908.1397" rel="nofollow">result</a> by myself and Julien Hendrickx that the matrix $p$-norm is NP-hard to approximate whenever $p$ is not $1,2,$ or $\infty$.</p> <p>On the positive side, the <a href="http://www2.isye.gatech.edu/~nemirovs/Daureen.pdf" rel="nofollow">M.S. thesis of Daureen Steinberg</a> has an efficient algorithm for computing the $p$-norm of a nonnegative matrix (see Remark 3.4 on page 48).</p> http://mathoverflow.net/questions/39148/efficiently-computing-a-matrixs-induced-p-norm/39180#39180 Answer by J. M. for Efficiently computing a matrix's induced p-norm J. M. 2010-09-18T01:06:18Z 2011-05-13T04:10:04Z <p>Nicholas Higham gives an <a href="http://dx.doi.org/10.1007/BF01396242" rel="nofollow">algorithm</a> for <em>estimating</em> 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?</p> <hr> <p>(added 5/13/2011)</p> <p>I posted a <em>Mathematica</em> translation of Higham's <a href="http://people.sc.fsu.edu/~jburkardt/m_src/test_matrix/pnorm.m" rel="nofollow">original MATLAB code</a> <a href="http://math.stackexchange.com/questions/37913/37939#37939" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/39148/efficiently-computing-a-matrixs-induced-p-norm/70449#70449 Answer by J.J. Green for Efficiently computing a matrix's induced p-norm J.J. Green 2011-07-15T16:27:00Z 2011-07-15T16:27:00Z <p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0024379511000589" rel="nofollow">paper</a> in <em>Lin. Alg. Appl</em> (and using it, refutes a long-standing conjecture of Matsaev).</p> <p>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).</p> <p>Drury's implementation for Visual C++ and Maple can be found <a href="http://www.math.mcgill.ca/drury/research/matsaev/matsaev.html" rel="nofollow">here</a>, and a C version targeted at Unix and with bindings for Matlab, Octave and Python can be found <a href="http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/maxmod.html" rel="nofollow">here</a>.</p>