KpNormDual

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

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

kpNormDual is a function that computes the dual of the (k,p)-norm of a vector or matrix. More explicitly, the (k,p)-norm of a vector $x = (x_1,x_2,\ldots,x_n)$ is \[\|x\|_{(k,p)} := \left(\sum_{j=1}^k \big|x_i^\downarrow\big|^p \right)^{1/p},\] where $(x_1^\downarrow,x_2^\downarrow,\ldots,x_n^\downarrow)$ is a rearrangement of the vector $x$ with the property that $|x_1^\downarrow| \geq |x_2^\downarrow| \geq \cdots \geq |x_n^\downarrow|$. Similarly, the (k,p)-norm of a matrix is the (k,p)-norm of its vector of singular values. This function computes the dual of this norm, which is fairly complicated and was derived in[1]. This function works with both full and sparse vectors and matrices.

Syntax

  • NRM = kpNormDual(X,K,P)

Argument descriptions

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

Examples

A simple 4-by-4 example

The (k,p)-norm of a matrix when k = 1 is simply the operator norm. The dual of the operator norm is the trace norm, so when k = 1 this function just returns the trace norm (regardless of p):

>> X = [1 1 1 1;1 2 3 4;1 4 9 16;1 8 27 64];
>> [kpNormDual(X,1,1), TraceNorm(X)]
 
ans =
 
   77.0015   77.0015

Similarly, if K = min(size(X)) and P = 2 then kpNorm(X,K,P) is the Frobenius norm, which is its own dual. Thus kpNormDual(X,K,2) decreases from the trace norm of X to its Frobenius norm as K increases:

>> [kpNormDual(X,1,2), TraceNorm(X)]
 
ans =
 
   77.0015   77.0015
 
>> kpNormDual(X,2,2)
 
ans =
 
   72.6903
 
>> kpNormDual(X,3,2)
 
ans =
 
   72.6505
 
>> [kpNormDual(X,4,2), norm(X,'fro')]
 
ans =
 
   72.6498   72.6498

Source code

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

  1. %%  KPNORMDUAL  Computes the dual of 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 = kpNormDual(X,K,P) is the dual of the (K,P)-norm of the vector or
  8. %   matrix X (see URL for details).
  9. %
  10. %   URL: http://www.qetlab.com/kpNormDual
  11.  
  12. %   requires: kpNorm.m
  13. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  14. %   package: QETLAB
  15. %   last updated: June 24, 2015
  16.  
  17. function nrm = kpNormDual(X,k,p)
  18.  
  19. sX = size(X);
  20. nX = min(sX);
  21. xX = max(sX);
  22.  
  23. % There are some special cases that we can compute slightly faster than
  24. % doing a full SVD, so we consider those cases separately.
  25. if((nX > 1 && k >= nX) && p == 2) % dual of the Frobenius norm is the Frobenius norm
  26.     nrm = norm(X,'fro');
  27. elseif((nX > 1 && k >= nX) && p == 1) % dual of the trace norm is the operator norm, which is computed faster by kpNorm.m, which uses svds in this case
  28.     nrm = kpNorm(X,1,1);
  29. elseif(p == Inf) % this case is needed to avoid errors, not for speed reasons: dual of operator norm is trace norm
  30.     nrm = kpNorm(X,xX,1);
  31. else % in all other cases, it seems like we have to compute all singular values or just brute-force our way with CVX
  32.  
  33.     % If X is a CVX variable, try to compute the norm in a way that won't
  34.     % piss off MATLAB.
  35.     if(isa(X,'cvx') == 1)
  36.         % Just compute the value via CVX using the definition of what it
  37.         % means to be the dual norm: optimize over the unit ball in the
  38.         % original norm.
  39.         cvx_begin quiet
  40.             cvx_precision best;
  41.             variable Y(sX(2),sX(1)) complex
  42.             maximize real(trace(X'*Y))
  43.             subject to
  44.                 kpNorm(Y,k,p) <= 1;
  45.         cvx_end
  46.  
  47.         nrm = real(cvx_optval);
  48.     else
  49.         if(nX == 1)
  50.             k = min(k,xX);
  51.             s = sort(X,'descend');
  52.         else
  53.             k = min(k,nX);
  54.             s = svd(full(X));
  55.         end
  56.  
  57.         for r=(k-1):-1:0
  58.             av = sum(s(r+1:end))/(k-r);
  59.             if(r == 0);break;end
  60.             if(s(r) > av);break;end
  61.         end
  62.         if(p == 1)
  63.             nrm = max([s(1),av]);
  64.         else
  65.             nrm = norm([s(1:r).',av*ones(1,k-r)],p/(p-1));
  66.         end
  67.     end
  68. end

References

  1. G.S. Mudholkar and M. Freimer. A structure theorem for the polars of unitarily invariant norms. Proc. Amer. Math. Soc., 95:331–337, 1985.