KyFanNorm

From QETLAB
Jump to: navigation, search
KyFanNorm
Computes the Ky Fan norm

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

KyFanNorm is a function that computes the Ky Fan k-norm of an operator (i.e., the sum of its k largest singular values): \[\|X\|_{(k)} := \sum_{j=1}^k \sigma_j^{\downarrow}(X).\] This function works with both full and sparse matrices, and can be used in the objective function or constraints of a CVX optimization problem.

Syntax

  • NRM = KyFanNorm(X,K)

Argument descriptions

  • X: An operator to have its Ky Fan K-norm computed.
  • K: A positive integer.

Examples

Equals the operator norm when K = 1 (but faster!)

The Ky Fan 1-norm is just the operator norm, which is implemented in MATLAB by the norm function. However, the KyFanNorm function is typically much faster than the norm function:

>> X = rand(2500);
>> tic; KyFanNorm(X,1)
   toc
 
ans =
 
       1250.2

Elapsed time is 0.861377 seconds.
 
>> tic; norm(X)
   toc
 
ans =
 
       1250.2

Elapsed time is 4.288788 seconds.

Can be used with CVX

This function can be used directly in constraints or the objective function of CVX problems. The following code snippet computes the minimum value of $\mathrm{Tr}(S\rho)$ over all density matrices $\rho$ satisfying $\|\rho\|_{(2)} \leq 3/4$, where $S$ is the swap operator.

>> cvx_begin sdp quiet
   variable rho(4,4) hermitian;
   minimize trace(rho*SwapOperator(2));
   subject to
       trace(rho) == 1;
       rho >= 0;
       KyFanNorm(rho,2) <= 3/4;
   cvx_end
   cvx_optval
 
cvx_optval =
 
   -0.2500
 
>> rho
 
rho =
 
   0.1250 + 0.0000i  -0.0000 + 0.0000i  -0.0000 + 0.0000i  -0.0000 + 0.0000i
  -0.0000 - 0.0000i   0.3750 + 0.0000i  -0.2500 + 0.0000i  -0.0000 + 0.0000i
  -0.0000 - 0.0000i  -0.2500 - 0.0000i   0.3750 + 0.0000i  -0.0000 + 0.0000i
  -0.0000 - 0.0000i  -0.0000 - 0.0000i  -0.0000 - 0.0000i   0.1250 + 0.0000i

Source code

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

  1. %%  KYFANNORM  Computes the Ky Fan k-norm of an operator
  2. %   This function has two required arguments:
  3. %     X: an operator
  4. %     K: a positive integer
  5. %
  6. %   NRM = KyFanNorm(X,K) is the Ky Fan K-norm of X.
  7. %
  8. %   URL: http://www.qetlab.com/KyFanNorm
  9.  
  10. %   requires: kpNorm.m
  11. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  12. %   package: QETLAB
  13. %   last updated: December 1, 2012
  14.  
  15. function nrm = KyFanNorm(X,k)
  16.  
  17. nrm = kpNorm(X,k,1);