InducedMatrixNorm

InducedMatrixNorm
Computes a lower bound of the induced p→q norm of a matrix
Other toolboxes required	none
Related functions	InducedSchattenNorm
Function category	Norms
Usable within CVX?	no

InducedMatrixNorm is a function that computes a randomized lower bound of the induced p→q norm of a matrix, defined as follows: \[\|B\|_{p\rightarrow q} := \max\big\{\|B\mathbf{x}\|_q : \|\mathbf{x}\|_p = 1 \big\},\] where \[\|\mathbf{x}\|_{p} := \left(\sum_i|x_i|^p\right)^{1/p}\] is the vector p-norm.

When p = q = 2, this is the usual operator norm, returned by MATLAB's built-in norm function. Similarly, when p = q = 1 or p = q = Inf, this is the maximum absolute column sum or maximum absolute row sum of the matrix, respectively, and for the matrix X it can be computed via the built-in MATLAB function norm(X,1) or norm(X,Inf). 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, which starts with a random vector and performs a local optimization based on that starting vector.

Syntax

• NRM = InducedMatrixNorm(X,P)
• NRM = InducedMatrixNorm(X,P,Q)
• NRM = InducedMatrixNorm(X,P,Q,TOL)
• NRM = InducedMatrixNorm(X,P,Q,TOL,V0)
• [NRM,V] = InducedMatrixNorm(X,P,Q,TOL,V0)

Argument descriptions

Input arguments

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

Output arguments

• NRM: A lower bound on the norm of X.
• V (optional): A vector with norm(V,P) = 1 such that norm(X*V,Q) = NRM (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:

>> 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

Source code

Click here to view this function's source code on github.