Jump to navigation Jump to search
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.


  • 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 (PQ)-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).


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 =


>> InducedMatrixNorm(X,3,5)

ans =


>> InducedMatrixNorm(X,5,3)

ans =


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

ans =


Source code

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