Cannot get a result

The issue can be reproduced in MATLAB with the data here using the following code snippet:

%  min norm( K2*X*K1'-M,'fro')^2+lambda*norm(X,'fro')^2
%   s.t. sum(X,1) = Sum1 ;   sum(X,2) = Sum2; all(X>=0) = true

variable S(size(K2,2),size(K1,2))
sum(S,1) == Sum1
sum(S,2) == Sum2

What’s strange is that even if I comment all constraints out, CVX still return +Inf.

Edit: New Data Can be Downloaded Here.
I regenerated a new data with a much smaller scale and convert the original problem to a one dimentional linear regression problem:Ax=b (A:2884086, b:288) . This time, all data were normalized to -1 ~ 1. But CVX still cannot calculate a results. even with no constraints.
I’d wanna know what’s wrong with my CVX.

Mosek reported dual infeasible. Because Mosek was provided the dual, CVX therefore determined the problem is (primal) infeasible.

sum(Sum1) = sum(Sum2), so `indeed the problem is actually feasible. Although the number they equal, 3.806119691049674e+06, is rather large, and not a really nice number numerically. But I don’t think that’s what’s causing the problem here.

At this point, I would like to congratulate you for setting a new record on this forum.The non-zero entries in K2 range from 1 (which is fine and dandy) all the way down to 9.88e-324, as well as multiple entries for each order of magnitude in between. That is a span of 323 orders of magnitude. (Side note: i don’t understand how this can be smaller than 2.225073858507201e-308; nevertheless, there it is). cond(K2) = 5.6e16, which is beyond the ability of double precision to handle (actually, cond(K2) = 2e17 when calculated in quad precision).

That is likely to cause all sorts of problems with double precision solvers, and quad precision as well. CVX’s reformulation to epigraph form places that matrix in the constraints. Mosek is a robust solver, but 323 orders of magnitude vastly exceeds what it can handle. Fortunately, Mosek warns about near-zero elements.

SeDuMi reported infeasibility after 34 iterations.

What does ^2 do in

min norm( K2XK1’-M,‘fro’)^2+lambda*norm(X,‘fro’)^2

Are they supposed to make the problem nicer? Or?
I would remove them.

You should adjust your lambda if you do. Most likely it should be closer to 1.

I want to implement the tikhonov regularization on my problem.

I’ve normalized all data and convert the original problem to a underdetermined linear regression problem
A*x = b
Now CVX returns NaN instead of Inf.
Data can be downloaded here.

Maybe Tikhonov only knew to solve problems with quadratic objective and that is the cause for ^2.

Why do not you post the solver log output. The data is fine but I usually do not spend on downloading data and running examples.

variable x(4096,1) 

is reported by Mosek to be infeasible,. Mosek also issues warnings about near zero elements, The matrix A has elements as small in magnitude as 3.782361859452318e-18, which is terrible. The maximum magnitude element of A is 2.205118450483101e+02. So the elements of A span 20 orders of magnitude: not good. Or as Gene Golub would have more emphatically labeled it in the Statistical Computing class I took from him: NFG. (I don’t know what he would have labeled the 323 orders of magnitude. The only labels he ever used in class were E, G, NG, NFG).

variable x(4096,1) 

is reported by Mosek to be dual infeasible. Mosek also issues warnings about near zero elements,

I calculated the unconstrained least squares solution of A*x = b by SVD (which is what pinv uses) and evaluated the norm of its residual

x_svd = pinv(A)*b;

ans =

This appears to show A*x= b is not undetermibned, but is overdetermined, so that A*x=b does not have an exact solution, and therefore CVX/Mosek’s determination of infeasibility of A*x == b is correct.

However, that appearance is INCORRECT!! I redid the SVD calculation and norm of residual evaluation using quad precision (34 digits) iin Advanpix Multiprecision Computing Toolbox; the resulting norm = 1.5e-24. So it now appears that Ax = b really is consistent. I then redid the SVD calculation in double quad precision (70 digits) and got norm of residual = 1.59 e-60, reaffirming the consistency of Ax=b.

cond(A) = 9e12 as evaluated in both double precision and quad precision. This is too badly conditioned for Mosek to handle, It s too badly conditioned for double precision SVD to handle accurately. However quad precision can handle it.

So in conclusion, CVX is not suitable to solve my problem, right?

Calling SDPT3 4.0: 12716 variables, 4104 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.

 num. of constraints = 4104
 dim. of sdp    var  =  4,   num. of sdp  blk  =  2
 dim. of socp   var  = 4386,   num. of socp blk  =  2
 dim. of linear var  = 8196
 dim. of free   var  = 128 *** convert ublk to lblk
 number of dense column in A = 288
   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|1.3e+02|1.2e+02|1.3e+08| 5.562471e+05  0.000000e+00| 0:0:01| spchol  1  1 
 1|0.644|0.642|4.6e+01|4.5e+01|5.4e+07| 7.790941e+05 -3.033814e+02| 0:0:07| spchol  2  1 
 2|0.692|0.600|1.4e+01|1.8e+01|2.6e+07| 9.296160e+05 -7.916997e+02| 0:0:13| spchol  1  1 
 3|0.846|0.684|2.2e+00|5.8e+00|9.9e+06| 9.774544e+05 -1.396634e+03| 0:0:20| spchol  1  1 
 4|0.638|0.597|7.9e-01|2.4e+00|4.9e+06| 9.491951e+05 -1.753426e+03| 0:0:26| spchol  1  1 
 5|0.485|0.350|4.0e-01|1.6e+00|3.7e+06| 8.701737e+05 -1.691654e+03| 0:0:33| spchol  1  1 
 6|0.581|0.362|1.7e-01|1.0e+00|2.7e+06| 7.189876e+05 -1.787481e+03| 0:0:40| spchol  1  1 
 7|0.513|0.311|8.3e-02|6.9e-01|2.1e+06| 5.798376e+05 -1.814552e+03| 0:0:46| spchol  1  1 
 8|0.156|0.518|7.0e-02|3.3e-01|1.3e+06| 5.428377e+05 -1.245342e+03| 0:0:53| spchol  1  1 
 9|0.472|0.318|3.7e-02|2.3e-01|9.8e+05| 4.032963e+05 -1.106541e+03| 0:0:59| spchol  1  1 
10|0.547|0.393|1.7e-02|1.4e-01|6.9e+05| 2.818432e+05 -8.953301e+02| 0:1:05| spchol  1  1 
11|0.497|0.342|8.4e-03|9.2e-02|5.2e+05| 2.128184e+05 -7.306646e+02| 0:1:12| spchol  1  1 
12|0.221|0.499|6.5e-03|4.8e-02|3.7e+05| 1.899484e+05 -5.048135e+02| 0:1:18| spchol  1  1 
13|0.261|0.320|4.8e-03|3.4e-02|3.0e+05| 1.625347e+05 -3.851480e+02| 0:1:24| spchol  1  1 
14|0.474|0.422|2.5e-03|2.0e-02|2.1e+05| 1.122167e+05 -2.898010e+02| 0:1:31| spchol  1  1 
15|0.635|0.333|9.3e-04|1.4e-02|1.6e+05| 6.937410e+04 -2.285660e+02| 0:1:37| spchol  1  1 
16|0.741|0.475|2.4e-04|7.6e-03|1.0e+05| 4.207055e+04 -1.595448e+02| 0:1:43| spchol  1  1 
17|0.338|0.332|1.6e-04|5.1e-03|8.1e+04| 3.616524e+04 -1.276339e+02| 0:1:50| spchol  1  1 
18|0.649|0.192|5.6e-05|4.5e-03|7.0e+04| 2.454744e+04 -1.121561e+02| 0:1:56| spchol  1  1 
19|1.000|0.598|2.1e-09|1.8e-03|3.7e+04| 1.386330e+04 -7.874949e+01| 0:2:03| spchol  1  1 
20|0.921|0.324|3.6e-09|1.2e-03|2.7e+04| 7.336624e+03 -6.317847e+01| 0:2:09| spchol  1  1 
21|1.000|0.361|5.4e-09|7.8e-04|2.1e+04| 5.486115e+03 -5.080506e+01| 0:2:16| spchol  1  1 
22|1.000|0.342|7.5e-09|5.2e-04|1.6e+04| 3.933483e+03 -4.284003e+01| 0:2:22| spchol  1  1 
23|1.000|0.505|6.5e-09|2.6e-04|1.0e+04| 3.111849e+03 -3.378239e+01| 0:2:29| spchol  1  1 
24|1.000|0.291|4.4e-09|1.8e-04|8.3e+03| 2.097031e+03 -2.876012e+01| 0:2:36| spchol  1  1 
25|1.000|0.605|4.6e-09|7.2e-05|3.9e+03| 1.091633e+03 -1.782165e+01| 0:2:43| spchol  1  1 
26|1.000|0.563|2.6e-09|3.1e-05|2.4e+03| 8.933746e+02 -1.322341e+01| 0:2:49| spchol  1  1 
27|1.000|0.488|3.7e-09|1.6e-05|1.4e+03| 4.629847e+02 -1.019899e+01| 0:2:55| spchol  1  1 
28|1.000|0.463|1.3e-08|8.6e-06|9.5e+02| 3.109440e+02 -8.209888e+00| 0:3:03| spchol  1  1 
29|1.000|0.404|1.9e-08|5.1e-06|6.2e+02| 1.629215e+02 -6.720489e+00| 0:3:10| spchol  1  1 
30|1.000|0.789|4.9e-07|1.1e-06|1.9e+02| 8.087539e+01 -4.230519e+00| 0:3:16| spchol  1  1 
31|1.000|0.339|1.9e-05|7.2e-07|1.4e+02| 4.293837e+01 -3.855030e+00| 0:3:22| spchol  1  1 
32|1.000|0.697|3.2e-05|2.2e-07|5.2e+01| 1.573946e+01 -3.007816e+00| 0:3:28| spchol  2  2 
33|1.000|0.819|1.6e-06|4.5e-08|1.5e+01| 4.489067e+00 -2.506782e+00| 0:3:35| spchol  2  2 
34|1.000|0.519|8.8e-06|2.5e-08|8.2e+00| 2.484661e-01 -2.376363e+00| 0:3:41| spchol  3  3 
35|1.000|0.821|3.3e-05|5.3e-09|2.5e+00|-1.104519e+00 -2.237375e+00| 0:3:48| spchol  3  3 
36|1.000|0.522|1.5e-04|2.9e-09|1.4e+00|-1.713413e+00 -2.207397e+00| 0:3:55| spchol  4  4 
37|1.000|0.801|3.5e-04|6.9e-10|4.8e-01|-1.959441e+00 -2.176403e+00| 0:4:02| spchol  7  7 
38|1.000|0.502|1.8e-03|1.1e-09|2.7e-01|-2.083067e+00 -2.168730e+00| 0:4:09| spchol  9 11 
39|1.000|0.789|2.7e-03|2.1e-09|9.7e-02|-2.118777e+00 -2.160405e+00| 0:4:16| spchol 20 21 
40|1.000|0.918|3.2e-03|2.8e-09|2.8e-02|-2.137976e+00 -2.157178e+00| 0:4:25| spchol 
  linsysolve: Schur complement matrix not positive definite
  switch to LU factor. splu 95 ^25 
  stop: primal infeas has deteriorated too much, 1.1e-02
41|0.029|0.029|3.2e-03|2.8e-09|2.8e-02|-2.137976e+00 -2.157178e+00| 0:4:35|
 number of iterations   = 41
 primal objective value = -2.13797560e+00
 dual   objective value = -2.15717848e+00
 gap := trace(XZ)       = 2.81e-02
 relative gap           = 5.30e-03
 actual relative gap    = 3.63e-03
 rel. primal infeas (scaled problem)   = 3.19e-03
 rel. dual     "        "       "      = 2.79e-09
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 1.6e+07, 4.9e+00, 6.4e+01
 norm(A), norm(b), norm(C) = 8.4e+03, 1.5e+00, 7.3e+01
 Total CPU time (secs)  = 275.13  
 CPU time per iteration = 6.71  
 termination code       = -7
 DIMACS: 3.2e-03  0.0e+00  7.7e-09  0.0e+00  3.6e-03  5.3e-03
Status: Failed
Optimal value (cvx_optval): NaN

That depends on exactly what you consider to be “your problem”.

With the data for your Tikhonov formulation, essentially nothing will be suitable. It is artificially generated in a way which makes it atrocious. Perhaps “actual” data (whatever that may be), is much easier for software to handle, and CVX and the solvers it calls could do a fine job.

The A*x=b formulation for which A is horribly conditioned, but there is an x which solves it exactly, can be handled by SVD, or probably QR, as well as backsolve, IF a high enough precision is used. But did you start with the x and artificially generate b as A*x? If so, being able to recover x is perhaps not of much practical utility for application to “actual” data.

I don’t understand what you’re really trying to do. Is the atrocious artificial data you have supplied just for development and test purposes, or is this the “actual” data you really want to deal with?