KpNormDual
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.
Contents
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.
%% KPNORMDUAL Computes the dual of 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 = kpNormDual(X,K,P) is the dual of the (K,P)-norm of the vector or
% matrix X (see URL for details).
%
% URL: http://www.qetlab.com/kpNormDual
% requires: kpNorm.m
% author: Nathaniel Johnston (nathaniel@njohnston.ca)
% package: QETLAB
% last updated: June 24, 2015
function nrm = kpNormDual(X,k,p)
sX = size(X);
nX = min(sX);
xX = max(sX);
% There are some special cases that we can compute slightly faster than
% doing a full SVD, so we consider those cases separately.
if((nX > 1 && k >= nX) && p == 2) % dual of the Frobenius norm is the Frobenius norm
nrm = norm(X,'fro');
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
nrm = kpNorm(X,1,1);
elseif(p == Inf) % this case is needed to avoid errors, not for speed reasons: dual of operator norm is trace norm
nrm = kpNorm(X,xX,1);
else % in all other cases, it seems like we have to compute all singular values or just brute-force our way with CVX
% 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)
% Just compute the value via CVX using the definition of what it
% means to be the dual norm: optimize over the unit ball in the
% original norm.
cvx_begin quiet
cvx_precision best;
variable Y(sX(2),sX(1)) complex
maximize real(trace(X'*Y))
subject to
kpNorm(Y,k,p) <= 1;
cvx_end
nrm = real(cvx_optval);
else
if(nX == 1)
k = min(k,xX);
s = sort(X,'descend');
else
k = min(k,nX);
s = svd(full(X));
end
for r=(k-1):-1:0
av = sum(s(r+1:end))/(k-r);
if(r == 0);break;end
if(s(r) > av);break;end
end
if(p == 1)
nrm = max([s(1),av]);
else
nrm = norm([s(1:r).',av*ones(1,k-r)],p/(p-1));
end
end
end
References
- ↑ G.S. Mudholkar and M. Freimer. A structure theorem for the polars of unitarily invariant norms. Proc. Amer. Math. Soc., 95:331–337, 1985.