KpNorm

	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.

%%  KPNORM    Computes the (k,p)-norm of a vector or matrix

%   This function has three required arguments:

```
%     X: a vector or matrix
```
```
%     K: a positive integer
```
```
%     P: a real number >= 1, or Inf
```
```
%
```

%   NRM = kpNorm(X,K,P) is the P-norm of the vector of the K largest

%   elements of the vector X (if X is a vector), or the P-norm of the

%   vector of the K largest singular values of X (if X is a matrix).

```
%
```
```
%   URL: http://www.qetlab.com/kpNorm
```
```
 
```
```
%   requires: nothing
```

%   author: Nathaniel Johnston (nathaniel@njohnston.ca)

```
%   package: QETLAB
```
```
%   last updated: June 24, 2015
```
```
 
```
```
function nrm = kpNorm(X,k,p)
```
```
 
```
```
    sX = size(X);
```
```
    nX = min(sX);
```
```
    xX = max(sX);
```
```
 
```

    % If X is a CVX variable, try to compute the norm in a way that won't piss

```
    % off MATLAB.
```
```
    if(isa(X,'cvx') == 1)
```

        if(((nX > 1 && k >= nX) || (nX == 1 && k >= xX)) && p == 2) % Frobenius norm or Euclidean norm of a vector

```
            nrm = norm(X,'fro');
```

        elseif(nX > 1 && (p == Inf || k == 1)) % operator norm

```
            nrm = norm(X);
```

        elseif(nX > 1 && k >= nX && p == 1) % trace norm

```
            nrm = norm_nuc(X);
```

        elseif(nX > 1 && p == 1) % Ky Fan k-norm

            nrm = lambda_sum_largest([zeros(sX(1)),X;X',zeros(sX(2))],min(k,nX));

        elseif(nX > 1) % some other norm that we can't implement in CVX quite so simply

            nrm = kpNorm_cvx(X,min(k,nX),p,nX,sX);

        elseif(nX == 1 && k >= xX) % vector p-norm

```
            nrm = norm(X,p);
```

        elseif(nX == 1 && p == Inf) % k is irrelevant here: all p=Inf vector norms are the same

```
            nrm = norm(X,Inf);
```

        elseif(nX == 1 && p == 1) % sum of k largest absolute values

```
            if(isreal(X))
```

                nrm = sum_largest([X(:);-X(:)],min(k,xX));

            else % is there a simpler way to handle the complex case??

                nrm = lambda_sum_largest([zeros(xX),diag(X);diag(X)',zeros(xX)],min(k,xX));

```
            end
```

        else % vector norm that is not a p-norm or k-norm

            nrm = kpNorm_cvx(diag(X),min(k,xX),p,xX,[xX,xX]);

```
        end
```
```
 
```

    % If X is *not* a CVX variable, compute the norm in a faster way that

    % won't break for people without CVX.

```
    else
```

        % If the requested norm is the Frobenius norm, compute it using MATLAB's

        % built-in Frobenius norm calculation, which is significantly faster than

```
        % computing singular values.
```

        if((nX > 1 && k >= nX) && p == 2)

```
            nrm = norm(X,'fro');
```
```
 
```

        % That's the one and only special case though; otherwise just compute the

        % norm from the singular values.

```
        else
```

            % p = Inf corresponds to the operator norm, which is calculated faster

```
            % via k = p = 1.
```
```
            if(p == Inf)
```
```
                k = 1;
```
```
                p = 1;
```
```
            end
```
```
 
```

            % Try to determine which method will be faster for computing k singular

            % values: svds (best if X is sparse and k is small) or svd (best if k

            % is large and/or X is full).

            adj = 20 + 1000*(~issparse(X));

```
 
```
```
            if(nX == 1)
```
```
                s = sort(X,'descend');
```
```
                s = s(1:min(k,xX));
```
```
            elseif(k <= ceil(nX/adj))
```
```
                s = svds(X,k);
```
```
            else
```
```
                s = svd(full(X));
```
```
                s = s(1:min(k,nX));
```
```
            end
```
```
            nrm = norm(s,p);
```
```
        end
```
```
    end
```
```
end
```
```
 
```

% This function computes an arbitrary (k,p)-norm in a CVX-friendly way.

% This is so that arbitrary (k,p)-norms can be used as the objective

% function or as constraints within other CVX problems.

```
% 
```

% This method is based on Madeleine Udell's wonderful post here:

% http://ask.cvxr.com/t/represent-schatten-p-norm-in-cvx/649/5

```
function nrm = kpNorm_cvx(X,k,p,nX,sX)
```

    bigX = [zeros(sX(1)),X;X',zeros(sX(2))];

```
 
```
```
    cvx_begin quiet
```
```
        cvx_precision default;
```
```
        variable s(nX,1)
```
```
        minimize norm(s(1:k),p)
```
```
        subject to
```
```
            for j = 1:nX-1
```

                lambda_sum_largest(bigX,j) <= sum(s(1:j));

```
                s(j) >= s(j+1);
```
```
            end
```

            lambda_sum_largest(bigX,nX) <= sum(s);

```
            s(nX) >= 0;
```
```
    cvx_end
```
```
 
```
```
    nrm = real(cvx_optval);
```
```
end
```

KpNorm

Contents

Syntax

Argument descriptions

Examples

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

Source code

Navigation menu

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Tools