Minimise ℓ1 Norm with ℓ2 Constraint¶
This example demonstrates the use of class
admm.bpdn.MinL1InL2Ball to solve the problem
\[\mathrm{argmin}_\mathbf{x} \| \mathbf{x} \|_1 \; \text{such that} \; \| D \mathbf{x} - \mathbf{s} \|_2 \leq \epsilon\]
where \(D\) is the dictionary, \(\mathbf{x}\) is the sparse representation, and \(\mathbf{s}\) is the signal to be represented. In this example this problem is used to estimate the reference sparse representation that generated a signal from a noisy version of the signal.
from __future__ import print_function
from builtins import input
import numpy as np
from sporco.admm import bpdn
from sporco import plot
plot.config_notebook_plotting()
Configure problem size, sparsity, and noise level.
N = 512 # Signal size
M = 4*N # Dictionary size
L = 32 # Number of non-zero coefficients in generator
sigma = 0.5 # Noise level
Construct random dictionary, reference random sparse representation, and test signal consisting of the synthesis of the reference sparse representation with additive Gaussian noise.
# Construct random dictionary and random sparse coefficients
np.random.seed(12345)
D = np.random.randn(N, M)
x0 = np.zeros((M, 1))
si = np.random.permutation(list(range(0, M-1)))
x0[si[0:L]] = np.random.randn(L, 1)
# Construct reference and noisy signal
s0 = D.dot(x0)
s = s0 + sigma*np.random.randn(N,1)
Set admm.bpdn.MinL1InL2Ball solver class options. The value
of \(\epsilon\) is estimated from the difference between the noisy
and reference signals.
epsilon = 1.1 * np.linalg.norm(s0 - s)
opt = bpdn.MinL1InL2Ball.Options({'Verbose': True, 'MaxMainIter': 500,
'RelStopTol': 1e-3, 'rho': 1e0,
'AutoRho': {'Enabled': False}})
Initialise and run admm.bpdn.MinL1InL2Ball object
b = bpdn.MinL1InL2Ball(D, s, epsilon, opt)
x = b.solve()
print("MinL1InL2Ball solve time: %.2fs" % b.timer.elapsed('solve'))
Itn Fnc Cnstr r s
--------------------------------------------
0 0.00e+00 1.15e+02 1.00e+00 4.95e+01
1 1.72e+02 8.84e+01 3.84e-01 4.92e+01
2 4.36e+01 3.86e+01 3.34e-01 4.56e+01
3 7.04e+01 0.00e+00 4.07e-02 1.00e+00
4 8.06e+01 0.00e+00 1.48e-02 1.00e+00
5 9.89e+01 0.00e+00 1.51e-02 1.00e+00
6 8.22e+01 0.00e+00 1.37e-02 1.00e+00
7 6.56e+01 0.00e+00 1.27e-02 1.00e+00
8 7.33e+01 0.00e+00 1.29e-02 1.00e+00
9 6.98e+01 0.00e+00 1.22e-02 1.00e+00
10 6.39e+01 0.00e+00 1.13e-02 1.00e+00
11 6.70e+01 0.00e+00 1.08e-02 1.00e+00
12 6.89e+01 0.00e+00 1.02e-02 1.00e+00
13 6.67e+01 0.00e+00 9.85e-03 1.00e+00
14 5.68e+01 2.78e-17 8.73e-03 1.00e+00
15 5.22e+01 2.78e-17 8.30e-03 1.00e+00
16 5.59e+01 2.78e-17 8.31e-03 1.00e+00
17 5.31e+01 3.10e-17 7.63e-03 1.00e+00
18 5.00e+01 6.21e-17 7.22e-03 1.00e+00
19 4.89e+01 5.72e-17 6.98e-03 1.00e+00
20 4.88e+01 6.21e-17 6.75e-03 1.00e+00
21 4.76e+01 1.24e-16 6.32e-03 1.00e+00
22 4.75e+01 6.80e-17 6.14e-03 1.00e+00
23 4.37e+01 5.55e-17 5.82e-03 1.00e+00
24 4.29e+01 1.24e-16 5.68e-03 1.00e+00
25 4.34e+01 6.80e-17 5.61e-03 1.00e+00
26 4.03e+01 6.21e-17 5.30e-03 1.00e+00
27 3.85e+01 2.78e-16 5.04e-03 1.00e+00
28 4.19e+01 2.50e-16 5.05e-03 1.00e+00
29 4.22e+01 2.78e-16 4.93e-03 1.00e+00
30 3.75e+01 2.22e-02 4.04e-03 5.33e-01
31 3.58e+01 4.46e-02 3.83e-03 4.96e-01
32 3.75e+01 1.36e-16 3.84e-03 5.10e-01
33 3.62e+01 2.97e-02 3.60e-03 4.74e-01
34 3.44e+01 2.62e-16 3.33e-03 4.73e-01
35 3.58e+01 1.80e-02 3.28e-03 4.35e-01
36 3.60e+01 1.76e-16 3.18e-03 4.33e-01
37 3.42e+01 1.17e-02 2.96e-03 4.08e-01
38 3.25e+01 2.10e-16 2.77e-03 4.10e-01
39 3.28e+01 7.83e-03 2.71e-03 3.90e-01
40 3.34e+01 3.09e-16 2.66e-03 3.86e-01
41 3.23e+01 4.79e-03 2.49e-03 3.68e-01
42 3.12e+01 2.90e-16 2.34e-03 3.60e-01
43 3.19e+01 3.50e-03 2.30e-03 3.42e-01
44 3.18e+01 2.02e-16 2.21e-03 3.33e-01
45 3.05e+01 2.37e-03 2.05e-03 3.18e-01
46 3.03e+01 2.72e-16 1.97e-03 3.09e-01
47 3.02e+01 1.32e-03 1.90e-03 2.97e-01
48 3.00e+01 2.72e-16 1.82e-03 2.89e-01
49 2.96e+01 1.47e-03 1.73e-03 2.77e-01
50 2.89e+01 1.63e-04 1.63e-03 2.66e-01
51 2.90e+01 1.13e-03 1.56e-03 2.53e-01
52 2.95e+01 3.00e-16 1.54e-03 2.42e-01
53 2.87e+01 5.69e-04 1.43e-03 2.31e-01
54 2.78e+01 1.50e-04 1.33e-03 2.22e-01
55 2.83e+01 7.57e-04 1.30e-03 2.13e-01
56 2.84e+01 5.63e-04 1.27e-03 2.04e-01
57 2.76e+01 7.34e-04 1.17e-03 1.95e-01
58 2.74e+01 3.12e-04 1.12e-03 1.86e-01
59 2.80e+01 4.33e-04 1.11e-03 1.77e-01
60 2.79e+01 3.00e-04 1.06e-03 1.68e-01
61 2.70e+01 6.17e-04 9.84e-04 1.60e-01
62 2.70e+01 5.99e-04 9.46e-04 1.52e-01
63 2.76e+01 6.42e-04 9.49e-04 1.45e-01
64 2.73e+01 3.83e-04 8.98e-04 1.39e-01
65 2.68e+01 3.13e-04 8.34e-04 1.33e-01
66 2.71e+01 3.61e-04 8.31e-04 1.27e-01
67 2.72e+01 5.09e-04 8.15e-04 1.20e-01
68 2.67e+01 5.85e-04 7.62e-04 1.15e-01
69 2.65e+01 6.06e-04 7.28e-04 1.09e-01
70 2.68e+01 4.91e-04 7.27e-04 1.04e-01
71 2.69e+01 4.20e-04 7.12e-04 1.00e-01
72 2.66e+01 3.44e-04 6.74e-04 9.69e-02
73 2.65e+01 4.26e-04 6.56e-04 9.33e-02
74 2.66e+01 5.16e-04 6.52e-04 8.95e-02
75 2.65e+01 5.22e-04 6.29e-04 8.60e-02
76 2.64e+01 5.26e-04 6.04e-04 8.29e-02
77 2.64e+01 4.94e-04 5.90e-04 8.03e-02
78 2.64e+01 4.71e-04 5.80e-04 7.82e-02
79 2.64e+01 4.38e-04 5.62e-04 7.63e-02
80 2.63e+01 4.03e-04 5.44e-04 7.46e-02
81 2.62e+01 4.35e-04 5.30e-04 7.27e-02
82 2.62e+01 4.76e-04 5.17e-04 7.08e-02
83 2.61e+01 4.86e-04 5.02e-04 6.92e-02
84 2.60e+01 4.69e-04 4.85e-04 6.78e-02
85 2.60e+01 4.55e-04 4.72e-04 6.65e-02
86 2.59e+01 4.29e-04 4.59e-04 6.54e-02
87 2.59e+01 4.13e-04 4.44e-04 6.43e-02
88 2.58e+01 4.05e-04 4.31e-04 6.32e-02
89 2.58e+01 3.79e-04 4.18e-04 6.20e-02
90 2.57e+01 3.71e-04 4.05e-04 6.09e-02
91 2.57e+01 3.72e-04 3.92e-04 5.97e-02
92 2.56e+01 3.79e-04 3.80e-04 5.86e-02
93 2.56e+01 3.91e-04 3.69e-04 5.75e-02
94 2.55e+01 3.79e-04 3.57e-04 5.65e-02
95 2.55e+01 3.52e-04 3.45e-04 5.54e-02
96 2.55e+01 3.22e-04 3.36e-04 5.43e-02
97 2.54e+01 3.10e-04 3.25e-04 5.32e-02
98 2.54e+01 2.98e-04 3.13e-04 5.21e-02
99 2.53e+01 3.00e-04 3.04e-04 5.10e-02
100 2.53e+01 2.89e-04 2.96e-04 4.99e-02
101 2.53e+01 3.09e-04 2.85e-04 4.87e-02
102 2.52e+01 3.11e-04 2.73e-04 4.75e-02
103 2.52e+01 3.06e-04 2.65e-04 4.64e-02
104 2.52e+01 2.61e-04 2.58e-04 4.52e-02
105 2.52e+01 2.08e-04 2.50e-04 4.41e-02
106 2.52e+01 1.77e-04 2.41e-04 4.30e-02
107 2.51e+01 1.95e-04 2.33e-04 4.18e-02
108 2.51e+01 2.43e-04 2.27e-04 4.07e-02
109 2.51e+01 2.59e-04 2.20e-04 3.96e-02
110 2.50e+01 2.34e-04 2.14e-04 3.85e-02
111 2.50e+01 1.89e-04 2.08e-04 3.74e-02
112 2.50e+01 1.50e-04 2.02e-04 3.64e-02
113 2.51e+01 1.39e-04 1.97e-04 3.54e-02
114 2.50e+01 1.50e-04 1.92e-04 3.44e-02
115 2.50e+01 1.64e-04 1.86e-04 3.34e-02
116 2.50e+01 1.71e-04 1.81e-04 3.24e-02
117 2.50e+01 1.67e-04 1.78e-04 3.15e-02
118 2.50e+01 1.52e-04 1.73e-04 3.06e-02
119 2.49e+01 1.29e-04 1.68e-04 2.98e-02
120 2.49e+01 1.10e-04 1.64e-04 2.90e-02
121 2.49e+01 1.03e-04 1.61e-04 2.82e-02
122 2.49e+01 1.10e-04 1.57e-04 2.74e-02
123 2.49e+01 1.21e-04 1.52e-04 2.67e-02
124 2.49e+01 1.25e-04 1.49e-04 2.60e-02
125 2.49e+01 1.18e-04 1.46e-04 2.53e-02
126 2.49e+01 1.06e-04 1.42e-04 2.46e-02
127 2.49e+01 9.45e-05 1.39e-04 2.40e-02
128 2.49e+01 8.74e-05 1.36e-04 2.35e-02
129 2.49e+01 8.61e-05 1.33e-04 2.29e-02
130 2.48e+01 8.66e-05 1.30e-04 2.24e-02
131 2.48e+01 8.89e-05 1.27e-04 2.18e-02
132 2.48e+01 9.23e-05 1.24e-04 2.13e-02
133 2.48e+01 9.33e-05 1.21e-04 2.08e-02
134 2.48e+01 8.88e-05 1.18e-04 2.04e-02
135 2.48e+01 7.95e-05 1.16e-04 1.99e-02
136 2.48e+01 7.15e-05 1.12e-04 1.95e-02
137 2.48e+01 7.05e-05 1.10e-04 1.91e-02
138 2.48e+01 7.44e-05 1.07e-04 1.87e-02
139 2.48e+01 7.88e-05 1.05e-04 1.83e-02
140 2.47e+01 8.02e-05 1.02e-04 1.79e-02
141 2.47e+01 7.78e-05 9.94e-05 1.75e-02
142 2.47e+01 7.19e-05 9.75e-05 1.72e-02
143 2.47e+01 6.71e-05 9.54e-05 1.68e-02
144 2.47e+01 6.66e-05 9.27e-05 1.65e-02
145 2.47e+01 6.83e-05 9.03e-05 1.61e-02
146 2.47e+01 7.00e-05 8.85e-05 1.58e-02
147 2.47e+01 7.04e-05 8.65e-05 1.54e-02
148 2.47e+01 6.91e-05 8.41e-05 1.51e-02
149 2.47e+01 6.68e-05 8.20e-05 1.48e-02
150 2.47e+01 6.47e-05 8.02e-05 1.45e-02
151 2.47e+01 6.40e-05 7.84e-05 1.42e-02
152 2.47e+01 6.50e-05 7.64e-05 1.39e-02
153 2.47e+01 6.67e-05 7.45e-05 1.36e-02
154 2.47e+01 6.74e-05 7.28e-05 1.33e-02
155 2.47e+01 6.61e-05 7.12e-05 1.30e-02
156 2.47e+01 6.38e-05 6.95e-05 1.27e-02
157 2.47e+01 6.17e-05 6.78e-05 1.24e-02
158 2.46e+01 6.09e-05 6.62e-05 1.22e-02
159 2.46e+01 6.13e-05 6.48e-05 1.19e-02
160 2.46e+01 6.21e-05 6.34e-05 1.17e-02
161 2.46e+01 6.29e-05 6.18e-05 1.14e-02
162 2.46e+01 6.33e-05 6.03e-05 1.12e-02
163 2.46e+01 6.29e-05 5.90e-05 1.09e-02
164 2.46e+01 6.14e-05 5.78e-05 1.07e-02
165 2.46e+01 5.90e-05 5.65e-05 1.05e-02
166 2.46e+01 5.66e-05 5.51e-05 1.02e-02
167 2.46e+01 5.40e-05 5.38e-05 1.00e-02
168 2.46e+01 5.32e-05 5.27e-05 9.81e-03
169 2.46e+01 5.47e-05 5.15e-05 9.59e-03
170 2.46e+01 5.71e-05 5.03e-05 9.37e-03
171 2.46e+01 5.81e-05 4.92e-05 9.16e-03
172 2.46e+01 5.62e-05 4.81e-05 8.96e-03
173 2.46e+01 5.24e-05 4.71e-05 8.78e-03
174 2.46e+01 4.94e-05 4.61e-05 8.60e-03
175 2.46e+01 4.89e-05 4.50e-05 8.42e-03
176 2.46e+01 5.03e-05 4.40e-05 8.24e-03
177 2.46e+01 5.15e-05 4.31e-05 8.07e-03
178 2.46e+01 5.05e-05 4.22e-05 7.89e-03
179 2.46e+01 4.85e-05 4.12e-05 7.73e-03
180 2.46e+01 4.72e-05 4.03e-05 7.57e-03
181 2.46e+01 4.70e-05 3.94e-05 7.41e-03
182 2.46e+01 4.68e-05 3.87e-05 7.26e-03
183 2.46e+01 4.58e-05 3.78e-05 7.11e-03
184 2.46e+01 4.44e-05 3.69e-05 6.96e-03
185 2.46e+01 4.31e-05 3.62e-05 6.82e-03
186 2.46e+01 4.24e-05 3.55e-05 6.68e-03
187 2.46e+01 4.19e-05 3.47e-05 6.55e-03
188 2.46e+01 4.15e-05 3.39e-05 6.42e-03
189 2.46e+01 4.09e-05 3.32e-05 6.29e-03
190 2.46e+01 4.03e-05 3.26e-05 6.16e-03
191 2.46e+01 3.96e-05 3.19e-05 6.04e-03
192 2.46e+01 3.88e-05 3.11e-05 5.92e-03
193 2.45e+01 3.77e-05 3.05e-05 5.80e-03
194 2.45e+01 3.66e-05 2.99e-05 5.68e-03
195 2.45e+01 3.55e-05 2.93e-05 5.57e-03
196 2.45e+01 3.46e-05 2.87e-05 5.46e-03
197 2.45e+01 3.39e-05 2.81e-05 5.36e-03
198 2.45e+01 3.36e-05 2.75e-05 5.25e-03
199 2.45e+01 3.35e-05 2.70e-05 5.15e-03
200 2.45e+01 3.31e-05 2.64e-05 5.05e-03
201 2.45e+01 3.23e-05 2.59e-05 4.95e-03
202 2.45e+01 3.11e-05 2.54e-05 4.85e-03
203 2.45e+01 2.99e-05 2.49e-05 4.76e-03
204 2.45e+01 2.91e-05 2.44e-05 4.66e-03
205 2.45e+01 2.86e-05 2.39e-05 4.57e-03
206 2.45e+01 2.81e-05 2.34e-05 4.49e-03
207 2.45e+01 2.75e-05 2.29e-05 4.40e-03
208 2.45e+01 2.70e-05 2.25e-05 4.32e-03
209 2.45e+01 2.65e-05 2.20e-05 4.23e-03
210 2.45e+01 2.61e-05 2.16e-05 4.15e-03
211 2.45e+01 2.56e-05 2.12e-05 4.07e-03
212 2.45e+01 2.49e-05 2.08e-05 3.99e-03
213 2.45e+01 2.42e-05 2.03e-05 3.91e-03
214 2.45e+01 2.35e-05 2.00e-05 3.84e-03
215 2.45e+01 2.29e-05 1.96e-05 3.77e-03
216 2.45e+01 2.24e-05 1.92e-05 3.70e-03
217 2.45e+01 2.20e-05 1.88e-05 3.63e-03
218 2.45e+01 2.15e-05 1.85e-05 3.56e-03
219 2.45e+01 2.11e-05 1.81e-05 3.49e-03
220 2.45e+01 2.08e-05 1.78e-05 3.43e-03
221 2.45e+01 2.06e-05 1.74e-05 3.36e-03
222 2.45e+01 2.03e-05 1.71e-05 3.30e-03
223 2.45e+01 1.98e-05 1.68e-05 3.24e-03
224 2.45e+01 1.92e-05 1.65e-05 3.17e-03
225 2.45e+01 1.85e-05 1.62e-05 3.12e-03
226 2.45e+01 1.79e-05 1.59e-05 3.06e-03
227 2.45e+01 1.75e-05 1.56e-05 3.00e-03
228 2.45e+01 1.73e-05 1.53e-05 2.95e-03
229 2.45e+01 1.73e-05 1.50e-05 2.89e-03
230 2.45e+01 1.73e-05 1.47e-05 2.84e-03
231 2.45e+01 1.72e-05 1.44e-05 2.79e-03
232 2.45e+01 1.69e-05 1.42e-05 2.73e-03
233 2.45e+01 1.63e-05 1.39e-05 2.68e-03
234 2.45e+01 1.56e-05 1.36e-05 2.63e-03
235 2.45e+01 1.48e-05 1.34e-05 2.59e-03
236 2.45e+01 1.43e-05 1.32e-05 2.54e-03
237 2.45e+01 1.43e-05 1.29e-05 2.49e-03
238 2.45e+01 1.45e-05 1.27e-05 2.45e-03
239 2.45e+01 1.48e-05 1.24e-05 2.40e-03
240 2.45e+01 1.47e-05 1.22e-05 2.36e-03
241 2.45e+01 1.42e-05 1.20e-05 2.31e-03
242 2.45e+01 1.36e-05 1.18e-05 2.27e-03
243 2.45e+01 1.32e-05 1.16e-05 2.23e-03
244 2.45e+01 1.29e-05 1.14e-05 2.19e-03
245 2.45e+01 1.27e-05 1.12e-05 2.15e-03
246 2.45e+01 1.26e-05 1.10e-05 2.11e-03
247 2.45e+01 1.25e-05 1.07e-05 2.08e-03
248 2.45e+01 1.24e-05 1.06e-05 2.04e-03
249 2.45e+01 1.24e-05 1.04e-05 2.00e-03
250 2.45e+01 1.22e-05 1.02e-05 1.97e-03
251 2.45e+01 1.19e-05 1.00e-05 1.93e-03
252 2.45e+01 1.16e-05 9.82e-06 1.90e-03
253 2.45e+01 1.13e-05 9.65e-06 1.86e-03
254 2.45e+01 1.12e-05 9.48e-06 1.83e-03
255 2.45e+01 1.11e-05 9.32e-06 1.80e-03
256 2.45e+01 1.09e-05 9.15e-06 1.77e-03
257 2.45e+01 1.07e-05 8.98e-06 1.73e-03
258 2.45e+01 1.06e-05 8.83e-06 1.70e-03
259 2.45e+01 1.04e-05 8.67e-06 1.67e-03
260 2.45e+01 1.04e-05 8.52e-06 1.64e-03
261 2.45e+01 1.03e-05 8.37e-06 1.61e-03
262 2.45e+01 1.02e-05 8.22e-06 1.59e-03
263 2.45e+01 9.95e-06 8.08e-06 1.56e-03
264 2.45e+01 9.71e-06 7.94e-06 1.53e-03
265 2.45e+01 9.47e-06 7.80e-06 1.50e-03
266 2.45e+01 9.28e-06 7.66e-06 1.48e-03
267 2.45e+01 9.15e-06 7.53e-06 1.45e-03
268 2.45e+01 9.09e-06 7.40e-06 1.43e-03
269 2.45e+01 9.06e-06 7.27e-06 1.40e-03
270 2.45e+01 9.02e-06 7.14e-06 1.38e-03
271 2.45e+01 8.89e-06 7.02e-06 1.35e-03
272 2.45e+01 8.71e-06 6.90e-06 1.33e-03
273 2.45e+01 8.50e-06 6.77e-06 1.31e-03
274 2.45e+01 8.29e-06 6.65e-06 1.28e-03
275 2.45e+01 8.08e-06 6.54e-06 1.26e-03
276 2.45e+01 7.91e-06 6.43e-06 1.24e-03
277 2.45e+01 7.85e-06 6.32e-06 1.22e-03
278 2.45e+01 7.86e-06 6.21e-06 1.20e-03
279 2.45e+01 7.83e-06 6.10e-06 1.18e-03
280 2.45e+01 7.73e-06 6.00e-06 1.15e-03
281 2.45e+01 7.56e-06 5.90e-06 1.13e-03
282 2.45e+01 7.37e-06 5.80e-06 1.12e-03
283 2.45e+01 7.20e-06 5.69e-06 1.10e-03
284 2.45e+01 7.06e-06 5.59e-06 1.08e-03
285 2.45e+01 6.94e-06 5.50e-06 1.06e-03
286 2.45e+01 6.86e-06 5.41e-06 1.04e-03
287 2.45e+01 6.78e-06 5.32e-06 1.02e-03
288 2.45e+01 6.69e-06 5.22e-06 1.01e-03
289 2.45e+01 6.58e-06 5.13e-06 9.88e-04
--------------------------------------------
MinL1InL2Ball solve time: 0.96s
Plot comparison of reference and recovered representations.
plot.plot(np.hstack((x0, x)), title='Sparse representation',
lgnd=['Reference', 'Reconstructed'])
Plot functional value, residuals, and rho
its = b.getitstat()
fig = plot.figure(figsize=(20, 5))
plot.subplot(1, 3, 1)
plot.plot(its.ObjFun, xlbl='Iterations', ylbl='Functional', fig=fig)
plot.subplot(1, 3, 2)
plot.plot(np.vstack((its.PrimalRsdl, its.DualRsdl)).T,
ptyp='semilogy', xlbl='Iterations', ylbl='Residual',
lgnd=['Primal', 'Dual'], fig=fig)
plot.subplot(1, 3, 3)
plot.plot(its.Rho, xlbl='Iterations', ylbl='Penalty Parameter', fig=fig)
fig.show()
