KpNorm

From QETLAB
Jump to: navigation, search
kpNorm
Computes the (k,p)-norm of a vector or matrix

Other toolboxes required none
Related functions kpNormDual
KyFanNorm
SchattenNorm
TraceNorm
Function category Norms
Usable within CVX? yes (convex)

kpNorm is a function that computes the (k,p)-norm of a vector or matrix, defined as follows: \[\|v\|_{k,p} := \left(\sum_{j=1}^k |v_j^{\downarrow}|^p \right)^{1/p}, \quad \|X\|_{k,p} := \left( \sum_{j=1}^k \sigma_j^{\downarrow}(X)^p \right)^{1/p}.\] In the case of a vector, this is the p-norm of the vector's k largest (in magnitude) entries. In the case of a matrix, this is the p-norm of the vector of its k largest singular values. This norm generalizes many well-known norms including the vector p-norms, the operator norm (when k = 1), the trace norm (when p = 1 and k is the size of X), the Schatten p-norms (when k is the size of X), and the Ky Fan k-norms (when p = 1). It works with both full and sparse vectors and matrices.

Syntax

  • NRM = kpNorm(X,K,P)

Argument descriptions

  • X: A vector or matrix to have its (K,P)-norm computed.
  • K: A positive integer.
  • P: A real number ≥ 1, or Inf.

Examples

Generalizes the operator, trace, Ky Fan, and Schatten norms

The (K,P)-norm of a matrix is simply the usual operator norm when K = 1 or P = Inf:

>> X = rand(3);
>> [norm(X), kpNorm(X,1,Inf), kpNorm(X,2,Inf), kpNorm(X,3,Inf), kpNorm(X,1,5)]
 
ans =
 
       1.0673       1.0673       1.0673       1.0673       1.0673

When P = 1 and K is the size of X, this norm reduces to the trace norm:

>> [kpNorm(X,3,1), TraceNorm(X)]
 
ans =
 
       1.6482       1.6482

More generally, when P = 1 this norm reduces to the Ky Fan K-norm:

>> [kpNorm(X,2,1), KyFanNorm(X,2)]
 
ans =
 
       1.5816       1.5816

Similarly, when K = min(size(X)) this norm reduces to the Schatten P-norm:

>> [kpNorm(X,3,4), SchattenNorm(X,4)]
 
ans =
 
       1.0814       1.0814

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

  1. %%  KPNORM    Computes the (k,p)-norm of a vector or matrix
  2. %   This function has three required arguments:
  3. %     X: a vector or matrix
  4. %     K: a positive integer
  5. %     P: a real number >= 1, or Inf
  6. %
  7. %   NRM = kpNorm(X,K,P) is the P-norm of the vector of the K largest
  8. %   elements of the vector X (if X is a vector), or the P-norm of the
  9. %   vector of the K largest singular values of X (if X is a matrix).
  10. %
  11. %   URL: http://www.qetlab.com/kpNorm
  12.  
  13. %   requires: nothing
  14. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  15. %   package: QETLAB
  16. %   last updated: June 24, 2015
  17.  
  18. function nrm = kpNorm(X,k,p)
  19.  
  20.     sX = size(X);
  21.     nX = min(sX);
  22.     xX = max(sX);
  23.  
  24.     % If X is a CVX variable, try to compute the norm in a way that won't piss
  25.     % off MATLAB.
  26.     if(isa(X,'cvx') == 1)
  27.         if(((nX > 1 && k >= nX) || (nX == 1 && k >= xX)) && p == 2) % Frobenius norm or Euclidean norm of a vector
  28.             nrm = norm(X,'fro');
  29.         elseif(nX > 1 && (p == Inf || k == 1)) % operator norm
  30.             nrm = norm(X);
  31.         elseif(nX > 1 && k >= nX && p == 1) % trace norm
  32.             nrm = norm_nuc(X);
  33.         elseif(nX > 1 && p == 1) % Ky Fan k-norm
  34.             nrm = lambda_sum_largest([zeros(sX(1)),X;X',zeros(sX(2))],min(k,nX));
  35.         elseif(nX > 1) % some other norm that we can't implement in CVX quite so simply
  36.             nrm = kpNorm_cvx(X,min(k,nX),p,nX,sX);
  37.         elseif(nX == 1 && k >= xX) % vector p-norm
  38.             nrm = norm(X,p);
  39.         elseif(nX == 1 && p == Inf) % k is irrelevant here: all p=Inf vector norms are the same
  40.             nrm = norm(X,Inf);
  41.         elseif(nX == 1 && p == 1) % sum of k largest absolute values
  42.             if(isreal(X))
  43.                 nrm = sum_largest([X(:);-X(:)],min(k,xX));
  44.             else % is there a simpler way to handle the complex case??
  45.                 nrm = lambda_sum_largest([zeros(xX),diag(X);diag(X)',zeros(xX)],min(k,xX));
  46.             end
  47.         else % vector norm that is not a p-norm or k-norm
  48.             nrm = kpNorm_cvx(diag(X),min(k,xX),p,xX,[xX,xX]);
  49.         end
  50.  
  51.     % If X is *not* a CVX variable, compute the norm in a faster way that
  52.     % won't break for people without CVX.
  53.     else
  54.         % If the requested norm is the Frobenius norm, compute it using MATLAB's
  55.         % built-in Frobenius norm calculation, which is significantly faster than
  56.         % computing singular values.
  57.         if((nX > 1 && k >= nX) && p == 2)
  58.             nrm = norm(X,'fro');
  59.  
  60.         % That's the one and only special case though; otherwise just compute the
  61.         % norm from the singular values.
  62.         else
  63.             % p = Inf corresponds to the operator norm, which is calculated faster
  64.             % via k = p = 1.
  65.             if(p == Inf)
  66.                 k = 1;
  67.                 p = 1;
  68.             end
  69.  
  70.             % Try to determine which method will be faster for computing k singular
  71.             % values: svds (best if X is sparse and k is small) or svd (best if k
  72.             % is large and/or X is full).
  73.             adj = 20 + 1000*(~issparse(X));
  74.  
  75.             if(nX == 1)
  76.                 s = sort(X,'descend');
  77.                 s = s(1:min(k,xX));
  78.             elseif(k <= ceil(nX/adj))
  79.                 s = svds(X,k);
  80.             else
  81.                 s = svd(full(X));
  82.                 s = s(1:min(k,nX));
  83.             end
  84.             nrm = norm(s,p);
  85.         end
  86.     end
  87. end
  88.  
  89. % This function computes an arbitrary (k,p)-norm in a CVX-friendly way.
  90. % This is so that arbitrary (k,p)-norms can be used as the objective
  91. % function or as constraints within other CVX problems.
  92. % 
  93. % This method is based on Madeleine Udell's wonderful post here:
  94. % http://ask.cvxr.com/t/represent-schatten-p-norm-in-cvx/649/5
  95. function nrm = kpNorm_cvx(X,k,p,nX,sX)
  96.     bigX = [zeros(sX(1)),X;X',zeros(sX(2))];
  97.  
  98.     cvx_begin quiet
  99.         cvx_precision default;
  100.         variable s(nX,1)
  101.         minimize norm(s(1:k),p)
  102.         subject to
  103.             for j = 1:nX-1
  104.                 lambda_sum_largest(bigX,j) <= sum(s(1:j));
  105.                 s(j) >= s(j+1);
  106.             end
  107.             lambda_sum_largest(bigX,nX) <= sum(s);
  108.             s(nX) >= 0;
  109.     cvx_end
  110.  
  111.     nrm = real(cvx_optval);
  112. end