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.admm import bpdn
from sporco import plot

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