# Performance time comparison between lambda_sum_largest and KyFanNorm(X,k)

I’m trying to compute an ‘extended’ Ky-Fan norm, as in, sum of the first k singular values + epsilon*(k+1)th value. I understand there are possibly two ways to do this:

1. lambda_sum_largest([zeros(n),X;X’,zeros(n)],k+epsilon) : The big advantage is that k can be a real scalar but maybe the flip side is forming the ‘extended’ matrix argument.

2. (1-epsilon)KyFanNorm(X,k) + epsilon*KyFanNorm(X,k+1) from the QETLAB package: I’ve to use this roundabout expression as k can only be a positive integer here. This results in two calls to the function (which increases the computation time)

Which is a better/faster way to go about?

Also, if I want to use the former, how can I avoid forming the extended matrix and instead maybe write an SVD routine first to get the ∑ matrix of the decomposition and call lambda_sum_largest(∑,k)?

QETLAB is at http://www.qetlab.com .

When called with a CVX variable or expression, rather than numeric, argument, `KyFanNorm` just calls `lambda_sum_largest` , as in your first version. In such case, it will accept non-integer k. So your first version is more efficient, as it only makes a single call to `KyFanNorm`. Or just make a single call to `KyFanNorm` with non-integer argument, which will incur a little extra MATLAB overhead from extra function calls to get to the `lambda_sum_largest`.

``````cvx_begin;variable X(4,4);
minimize(KyFanNorm(X,3.2))
X==eye(4);
cvx_end

Calling SDPT3 4.0: 74 variables, 36 equality constraints
------------------------------------------------------------

num. of constraints = 36
dim. of sdp    var  = 16,   num. of sdp  blk  =  2
dim. of linear var  =  1
dim. of free   var  =  1 *** convert ublk to lblk
*******************************************************************
SDPT3: Infeasible path-following algorithms
*******************************************************************
version  predcorr  gam  expon  scale_data
HKM      1      0.000   1        0
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
0|0.000|0.000|6.7e-01|6.4e+00|1.8e+03| 9.000000e+01  0.000000e+00| 0:0:00| chol  1  1
1|1.000|0.983|5.2e-07|1.8e-01|1.2e+02| 7.860765e+01  4.717366e-01| 0:0:00| chol  1  1
2|1.000|0.373|4.4e-07|1.1e-01|2.9e+01| 2.111162e+01  5.092962e-01| 0:0:00| chol  1  1
3|0.993|0.433|2.3e-07|6.4e-02|7.8e+00| 7.017229e+00  8.723023e-01| 0:0:00| chol  1  1
4|0.942|0.928|1.9e-08|4.7e-03|7.3e-01| 3.721233e+00  3.056044e+00| 0:0:00| chol  1  1
5|0.969|0.908|9.1e-10|4.3e-04|4.0e-02| 3.218773e+00  3.184744e+00| 0:0:00| chol  1  1
6|0.988|0.987|2.6e-10|6.1e-06|5.0e-04| 3.200235e+00  3.199819e+00| 0:0:00| chol  1  1
7|0.989|0.989|2.7e-11|2.9e-06|1.9e-05| 3.200003e+00  3.199998e+00| 0:0:00| chol  2  2
8|1.000|0.989|1.3e-13|1.1e-07|7.0e-07| 3.200000e+00  3.200000e+00| 0:0:00| chol  2  2
9|1.000|0.989|1.1e-12|4.1e-09|2.6e-08| 3.200000e+00  3.200000e+00| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations   =  9
primal objective value =  3.20000001e+00
dual   objective value =  3.20000000e+00
gap := trace(XZ)       = 2.63e-08
relative gap           = 3.55e-09
actual relative gap    = 1.03e-09
rel. primal infeas (scaled problem)   = 1.05e-12
rel. dual     "        "       "      = 4.08e-09
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual     "        "       "      = 0.00e+00
norm(X), norm(y), norm(Z) = 4.1e+00, 2.0e+00, 2.8e+00
norm(A), norm(b), norm(C) = 8.7e+00, 3.0e+00, 6.4e+00
Total CPU time (secs)  = 0.21
CPU time per iteration = 0.02
termination code       =  0
DIMACS: 1.6e-12  0.0e+00  6.2e-09  0.0e+00  1.0e-09  3.5e-09
-------------------------------------------------------------------

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +3.2
``````

Changing the objective to `minimize(lambda_sum_largest([zeros(n),X;X',zeros(n)],3.2))` produces the same result, because that is what the KyFanNorm call is converted to.

You’re looking at the numeric version of lambda_sum_largest . The version which is applied to CVX variables and expressions is in functions/@cvx. You will see in the “guts”, a semidefinite optimization problem solved

``````cvx_begin
variable S(n,n) symmetric
S == semidefinite(n); %#ok
minimize( k * lambda_max( x - S ) + trace( S ) );
cvx_end``````