Nathaniel: added external link

2016-01-12T02:40:33Z

added external link

Nathaniel: Created page with "{{Function |name=InducedMatrixNorm |desc=Computes a lower bound of the induced p→q norm of a matrix |rel=InducedSchattenNorm |cat=Norms |u..."

2016-01-06T19:25:21Z

Created page with "{{Function |name=InducedMatrixNorm |desc=Computes a lower bound of the induced p→q norm of a matrix |rel=InducedSchattenNorm |cat=Norms |u..."

New page

{{Function
|name=InducedMatrixNorm
|desc=Computes a lower bound of the induced p→q norm of a matrix
|rel=[[InducedSchattenNorm]]
|cat=[[List of functions#Norms|Norms]]
|upd=January 6, 2016
|cvx=no}}
<tt>'''InducedMatrixNorm'''</tt> is a [[List of functions|function]] that computes a randomized lower bound of the induced p→q norm of a matrix, defined as follows:
: <math>\|B\|_{p\rightarrow q} := \max\big\{\|B\mathbf{x}\|_q : \|\mathbf{x}\|_p = 1 \big\},</math>
where
: <math>\|\mathbf{x}\|_{p} := \left(\sum_i|x_i|^p\right)^{1/p}</math>
is the vector p-norm.

When <tt>p = q = 2</tt>, this is the usual operator norm, returned by MATLAB's built-in <tt>norm</tt> function. Similarly, when <tt>p = q = 1</tt> or <tt>p = q = Inf</tt>, this is the maximum absolute column sum or maximum absolute row sum of the matrix, respectively, and for the matrix <tt>X</tt> it can be computed via the built-in MATLAB function <tt>norm(X,1)</tt> or <tt>norm(X,Inf)</tt>. However, it most other cases this norm is hard to compute, and this function provides a randomized lower bound of it.

The lower bound is found via the algorithm described here (link to be filled in), which starts with a random vector and performs a local optimization based on that starting vector.

==Syntax==
* <tt>NRM = InducedMatrixNorm(X,P)</tt>
* <tt>NRM = InducedMatrixNorm(X,P,Q)</tt>
* <tt>NRM = InducedMatrixNorm(X,P,Q,TOL)</tt>
* <tt>NRM = InducedMatrixNorm(X,P,Q,TOL,V0)</tt>
* <tt>[NRM,V] = InducedMatrixNorm(X,P,Q,TOL,V0)</tt>

==Argument descriptions==
===Input arguments===
* <tt>X</tt>: A matrix to have its induced (<tt>P</tt>→<tt>Q</tt>)-norm computed.
* <tt>P</tt>: A real number ≥ 1, or <tt>Inf</tt>.
* <tt>Q</tt> (optional, default equals <tt>P</tt>): A real number ≥ 1, or <tt>Inf</tt>.
* <tt>TOL</tt> (optional, default equals <tt>sqrt(eps)</tt>): Numerical tolerance used throughout the script.
* <tt>V0</tt> (optional, default is randomly-generated): A vector to start the numerical search from.

===Output arguments===
* <tt>NRM</tt>: A lower bound on the norm of <tt>X</tt>.
* <tt>V</tt> (optional): A vector with <tt>norm(V,P) = 1</tt> such that <tt>norm(X*V,Q) = NRM</tt> (i.e., a vector that attains the local maximum that was found).

==Examples==
===Induced norms of the identity matrix===
The n-by-n identity matrix has induced p→q-norm equal to $\max\{n^{1/q - 1/p}, 1\}$, which this function finds exactly:
<syntaxhighlight>
>> X = eye(5);
>> InducedMatrixNorm(X,3,3)

ans =

1

>> InducedMatrixNorm(X,3,5)

ans =

1

>> InducedMatrixNorm(X,5,3)

ans =

1.2394

>> 5^(1/3 - 1/5)

ans =

1.2394
</syntaxhighlight>

{{SourceCode|name=InducedMatrixNorm}}

@@ Line 14: / Line 14: @@
 When <tt>p = q = 2</tt>, this is the usual operator norm, returned by MATLAB's built-in <tt>norm</tt> function. Similarly, when <tt>p = q = 1</tt> or <tt>p = q = Inf</tt>, this is the maximum absolute column sum or maximum absolute row sum of the matrix, respectively, and for the matrix <tt>X</tt> it can be computed via the built-in MATLAB function <tt>norm(X,1)</tt> or <tt>norm(X,Inf)</tt>. However, it most other cases this norm is hard to compute, and this function provides a randomized lower bound of it.
-The lower bound is found via the algorithm described here (link to be filled in), which starts with a random vector and performs a local optimization based on that starting vector.
+The lower bound is found via the algorithm described [http://www.njohnston.ca/2016/01/how-to-compute-hard-to-compute-matrix-norms/ here], which starts with a random vector and performs a local optimization based on that starting vector.
 ==Syntax==

InducedMatrixNorm - Revision history

Nathaniel: added external link

Nathaniel: Created page with "{{Function |name=InducedMatrixNorm |desc=Computes a lower bound of the induced p→q norm of a matrix |rel=InducedSchattenNorm |cat=Norms |u..."