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