Hi,
I’m using Lasso to solve a linear problem, but as the data size is quite large it’s taking a relatively long time. (code below)
I’m using SDPT3, and I get no output to the command window for ~15 minutes before the solver appears to kick-in. At this point the solver runs in about half a minute, and I get an answer.
Is there a way to speed this up? Or if I want to test the reconstruction for different values of lambda, or a different signal, is there a way to speed this up?
I’m using the following for the linear problem s = Ax.
s is an (m by 1) signal.
x is our desired image indices (n by 1).
A is a highly sparse measurement matrix (n by m).
lambda is the regularisation parameter.
Is there a way to speed this up if I want to test multiple values of lambda, and multiple values of s?
_cvx_begin_
_ variable x(n)_
_ minimize( norm((A’ x-s),2) + lambdanorm(x,1) )_
_ cvx_end_
Thanks in advance!
The output is as follows:
Calling SDPT3 4.0: 464302 variables, 1579 equality constraints
num. of constraints = 1579
dim. of socp var = 464302, num. of socp blk = 231362
SDPT3: Infeasible path-following algorithms
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime
0|0.000|0.000|1.0e+00|4.8e+02|6.7e+13| 1.381538e+11 0.000000e+00| 0:0:01| spchol 1 1
1|1.000|0.989|6.4e-12|6.0e+00|9.6e+11| 1.373202e+11 3.892478e+05| 0:0:02| spchol 1 1
2|1.000|1.000|8.3e-13|2.5e-01|1.2e+11| 9.281494e+10 4.358731e+05| 0:0:03| spchol 1 1
3|0.884|1.000|8.3e-12|1.2e-01|1.4e+10| 1.217439e+10 1.456265e+06| 0:0:04| spchol 1 1
4|1.000|0.946|1.8e-11|6.6e-02|1.1e+09| 1.035053e+09 3.443195e+06| 0:0:05| spchol 1 1
5|0.946|0.944|2.1e-11|3.3e-02|5.9e+07| 6.030974e+07 3.507356e+06| 0:0:06| spchol 2 2
6|0.470|0.518|3.5e-11|2.4e-02|4.1e+07| 4.316651e+07 3.540966e+06| 0:0:07| spchol 2 2
7|0.793|0.323|1.6e-11|1.9e-02|2.1e+07| 2.393797e+07 3.553191e+06| 0:0:08| spchol 2 2
8|1.000|0.480|5.7e-12|1.2e-02|8.9e+06| 1.239039e+07 3.574175e+06| 0:0:09| spchol 1 1
9|0.654|1.000|2.8e-12|2.0e-03|3.9e+06| 7.508395e+06 3.571074e+06| 0:0:10| spchol 1 1
10|0.945|0.775|5.4e-13|1.2e-03|7.5e+05| 4.337007e+06 3.584115e+06| 0:0:11| spchol 1 1
11|1.000|0.801|7.8e-12|6.3e-04|1.5e+05| 3.732528e+06 3.586574e+06| 0:0:12| spchol 1 1
12|0.834|0.623|8.3e-12|3.9e-04|3.4e+04| 3.620334e+06 3.586799e+06| 0:0:14| spchol 2 2
13|0.898|0.533|8.5e-13|2.5e-04|7.6e+03| 3.594233e+06 3.586820e+06| 0:0:15| spchol 2 2
14|1.000|0.739|6.5e-15|1.1e-04|1.4e+03| 3.588100e+06 3.586791e+06| 0:0:16| spchol 2 2
15|0.815|0.747|3.5e-14|5.1e-05|3.9e+02| 3.587097e+06 3.586756e+06| 0:0:17| spchol 2 2
16|0.670|0.567|5.5e-13|2.2e-05|1.7e+02| 3.586887e+06 3.586733e+06| 0:0:18| spchol 2 2
17|1.000|0.699|2.0e-12|6.6e-06|5.2e+01| 3.586766e+06 3.586721e+06| 0:0:19| spchol 2 3
18|0.825|0.761|1.1e-12|1.6e-06|1.9e+01| 3.586734e+06 3.586717e+06| 0:0:20| spchol 3 3
19|0.826|0.784|1.1e-12|3.4e-07|7.3e+00| 3.586723e+06 3.586716e+06| 0:0:21| spchol 3 3
20|0.857|0.839|3.5e-12|5.5e-08|2.6e+00| 3.586718e+06 3.586715e+06| 0:0:22| spchol 4 4
21|0.999|0.960|6.5e-12|2.2e-09|5.5e-01| 3.586716e+06 3.586715e+06| 0:0:23| spchol 5 5
22|0.984|0.970|1.9e-13|6.7e-11|1.3e-02| 3.586715e+06 3.586715e+06| 0:0:24|
stop: max(relative gap, infeasibilities) < 1.49e-08
number of iterations = 22
primal objective value = 3.58671535e+06
dual objective value = 3.58671534e+06
gap := trace(XZ) = 1.30e-02
relative gap = 1.81e-09
actual relative gap = 1.80e-09
rel. primal infeas (scaled problem) = 1.87e-13
rel. dual " " " = 6.68e-11
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 5.0e+06, 1.0e+00, 1.2e+02
norm(A), norm(b), norm© = 1.2e+03, 3.6e+06, 1.2e+02
Total CPU time (secs) = 23.61
CPU time per iteration = 1.07
termination code = 0
DIMACS: 2.0e-13 0.0e+00 4.0e-09 0.0e+00 1.8e-09 1.8e-09
Status: Solved
Optimal value (cvx_optval): +3.58672e+06