# 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
from builtins import range

import numpy as np

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  0.00e+00  8.73e-03  1.00e+00
15  5.22e+01  0.00e+00  8.30e-03  1.00e+00
16  5.59e+01  0.00e+00  8.31e-03  1.00e+00
17  5.31e+01  0.00e+00  7.63e-03  1.00e+00
18  5.00e+01  0.00e+00  7.22e-03  1.00e+00
19  4.89e+01  0.00e+00  6.98e-03  1.00e+00
20  4.88e+01  0.00e+00  6.75e-03  1.00e+00
21  4.76e+01  0.00e+00  6.32e-03  1.00e+00
22  4.75e+01  0.00e+00  6.14e-03  1.00e+00
23  4.37e+01  0.00e+00  5.82e-03  1.00e+00
24  4.29e+01  0.00e+00  5.68e-03  1.00e+00
25  4.34e+01  0.00e+00  5.61e-03  1.00e+00
26  4.03e+01  0.00e+00  5.30e-03  1.00e+00
27  3.85e+01  0.00e+00  5.04e-03  1.00e+00
28  4.19e+01  0.00e+00  5.05e-03  1.00e+00
29  4.22e+01  0.00e+00  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  0.00e+00  3.84e-03  5.10e-01
33  3.62e+01  2.97e-02  3.60e-03  4.74e-01
34  3.44e+01  0.00e+00  3.33e-03  4.73e-01
35  3.58e+01  1.80e-02  3.28e-03  4.35e-01
36  3.60e+01  0.00e+00  3.18e-03  4.33e-01
37  3.42e+01  1.17e-02  2.96e-03  4.08e-01
38  3.25e+01  0.00e+00  2.77e-03  4.10e-01
39  3.28e+01  7.83e-03  2.71e-03  3.90e-01
40  3.34e+01  0.00e+00  2.66e-03  3.86e-01
41  3.23e+01  4.79e-03  2.49e-03  3.68e-01
42  3.12e+01  0.00e+00  2.34e-03  3.60e-01
43  3.19e+01  3.50e-03  2.30e-03  3.42e-01
44  3.18e+01  0.00e+00  2.21e-03  3.33e-01
45  3.05e+01  2.37e-03  2.05e-03  3.18e-01
46  3.03e+01  0.00e+00  1.97e-03  3.09e-01
47  3.02e+01  1.32e-03  1.90e-03  2.97e-01
48  3.00e+01  0.00e+00  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  0.00e+00  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.85e-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.85e-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.43s


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()