# KpNormDual

 Other toolboxes required kpNormDual Computes the dual of the (k,p)-norm of a vector or matrix none kpNormKyFanNormSchattenNormTraceNorm Norms 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.