# KpNorm

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