Basis Pursuit DeNoising

This example demonstrates the use of class fista.bpdn.BPDN to solve the Basis Pursuit DeNoising (BPDN) problem [11]

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2 + \lambda \| \mathbf{x} \|_1 \;,\]

where \(D\) is the dictionary, \(\mathbf{x}\) is the sparse representation, and \(\mathbf{s}\) is the signal to be represented. In this example the BPDN 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.fista import bpdn
from sporco import util
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 BPDN solver with standard FISTA backtracking.

L_sc = 9.e2
opt = bpdn.BPDN.Options({'Verbose': True, 'MaxMainIter': 50,
                    'BackTrack': {'Enabled': True }, 'L': L_sc})


lmbda = 2.98e1

print("")
b = bpdn.BPDN(D, s, lmbda, opt)
x = b.solve()

print("BPDN standard FISTA backtracking solve time: %.2fs" %
      b.timer.elapsed('solve'))
print("")
Itn   Fnc       DFid      Regℓ1     Rsdl      F         Q         It_Bt  L
---------------------------------------------------------------------------------
   0  3.08e+03  1.59e+03  5.00e+01  1.68e+00  1.59e+03  2.24e+03      8  3.22e+03
   1  2.45e+03  8.43e+02  5.39e+01  4.96e-01  8.43e+02  1.05e+03      1  3.22e+03
   2  2.16e+03  4.93e+02  5.61e+01  2.61e-01  4.93e+02  5.69e+02      1  3.22e+03
   3  1.99e+03  3.48e+02  5.52e+01  1.79e-01  3.48e+02  3.94e+02      1  3.22e+03
   4  1.86e+03  2.77e+02  5.31e+01  1.48e-01  2.77e+02  3.09e+02      1  3.22e+03
   5  1.75e+03  2.40e+02  5.07e+01  1.31e-01  2.40e+02  2.66e+02      1  3.22e+03
   6  1.65e+03  2.21e+02  4.81e+01  1.20e-01  2.21e+02  2.42e+02      1  3.22e+03
   7  1.56e+03  2.08e+02  4.55e+01  1.11e-01  2.08e+02  2.27e+02      1  3.22e+03
   8  1.48e+03  1.97e+02  4.31e+01  1.05e-01  1.97e+02  2.13e+02      1  3.22e+03
   9  1.41e+03  1.86e+02  4.09e+01  9.78e-02  1.86e+02  2.00e+02      1  3.22e+03
  10  1.33e+03  1.77e+02  3.88e+01  9.04e-02  1.77e+02  1.90e+02      1  3.22e+03
  11  1.26e+03  1.69e+02  3.67e+01  8.70e-02  1.69e+02  1.81e+02      1  3.22e+03
  12  1.20e+03  1.61e+02  3.49e+01  8.39e-02  1.61e+02  1.71e+02      1  3.22e+03
  13  1.14e+03  1.51e+02  3.32e+01  8.11e-02  1.51e+02  1.60e+02      1  3.22e+03
  14  1.09e+03  1.42e+02  3.17e+01  7.88e-02  1.42e+02  1.51e+02      1  3.22e+03
  15  1.03e+03  1.34e+02  3.02e+01  7.34e-02  1.34e+02  1.42e+02      1  3.22e+03
  16  9.86e+02  1.28e+02  2.88e+01  6.89e-02  1.28e+02  1.35e+02      1  3.22e+03
  17  9.43e+02  1.21e+02  2.76e+01  7.12e-02  1.21e+02  1.29e+02      1  3.22e+03
  18  9.04e+02  1.13e+02  2.66e+01  6.89e-02  1.13e+02  1.20e+02      1  3.22e+03
  19  8.72e+02  1.05e+02  2.57e+01  6.23e-02  1.05e+02  1.11e+02      1  3.22e+03
  20  8.49e+02  9.79e+01  2.52e+01  6.41e-02  9.79e+01  1.04e+02      1  3.22e+03
  21  8.34e+02  8.95e+01  2.50e+01  6.70e-02  8.95e+01  9.57e+01      1  3.22e+03
  22  8.27e+02  8.40e+01  2.49e+01  5.62e-02  8.40e+01  8.83e+01      1  3.22e+03
  23  8.26e+02  7.99e+01  2.50e+01  6.01e-02  7.99e+01  8.49e+01      1  3.22e+03
  24  8.28e+02  7.75e+01  2.52e+01  5.90e-02  7.75e+01  8.24e+01      1  3.22e+03
  25  8.30e+02  7.62e+01  2.53e+01  4.73e-02  7.62e+01  7.94e+01      1  3.22e+03
  26  8.30e+02  7.62e+01  2.53e+01  3.76e-02  7.62e+01  7.81e+01      1  3.22e+03
  27  8.28e+02  7.68e+01  2.52e+01  3.18e-02  7.68e+01  7.82e+01      1  3.22e+03
  28  8.26e+02  7.86e+01  2.51e+01  2.39e-02  7.86e+01  7.95e+01      1  3.22e+03
  29  8.23e+02  8.17e+01  2.49e+01  1.82e-02  8.17e+01  8.21e+01      1  3.22e+03
  30  8.22e+02  8.53e+01  2.47e+01  1.33e-02  8.53e+01  8.56e+01      1  3.22e+03
  31  8.21e+02  8.89e+01  2.46e+01  1.06e-02  8.89e+01  8.91e+01      1  3.22e+03
  32  8.20e+02  9.16e+01  2.45e+01  1.06e-02  9.16e+01  9.18e+01      1  3.22e+03
  33  8.20e+02  9.31e+01  2.44e+01  1.02e-02  9.31e+01  9.32e+01      1  3.22e+03
  34  8.20e+02  9.34e+01  2.44e+01  9.82e-03  9.34e+01  9.35e+01      1  3.22e+03
  35  8.20e+02  9.28e+01  2.44e+01  9.05e-03  9.28e+01  9.29e+01      1  3.22e+03
  36  8.20e+02  9.19e+01  2.44e+01  8.34e-03  9.19e+01  9.20e+01      1  3.22e+03
  37  8.20e+02  9.08e+01  2.45e+01  8.33e-03  9.08e+01  9.09e+01      1  3.22e+03
  38  8.20e+02  8.98e+01  2.45e+01  8.47e-03  8.98e+01  8.99e+01      1  3.22e+03
  39  8.20e+02  8.92e+01  2.45e+01  6.82e-03  8.92e+01  8.93e+01      1  3.22e+03
  40  8.20e+02  8.89e+01  2.45e+01  5.97e-03  8.89e+01  8.90e+01      1  3.22e+03
  41  8.20e+02  8.87e+01  2.45e+01  5.24e-03  8.87e+01  8.88e+01      1  3.22e+03
  42  8.20e+02  8.85e+01  2.45e+01  4.90e-03  8.85e+01  8.86e+01      1  3.22e+03
  43  8.20e+02  8.83e+01  2.45e+01  4.37e-03  8.83e+01  8.84e+01      1  3.22e+03
  44  8.20e+02  8.83e+01  2.45e+01  3.19e-03  8.83e+01  8.83e+01      1  3.22e+03
  45  8.20e+02  8.82e+01  2.45e+01  3.12e-03  8.82e+01  8.82e+01      1  3.22e+03
  46  8.20e+02  8.81e+01  2.45e+01  3.90e-03  8.81e+01  8.82e+01      1  3.22e+03
  47  8.20e+02  8.80e+01  2.45e+01  3.57e-03  8.80e+01  8.80e+01      1  3.22e+03
  48  8.20e+02  8.79e+01  2.46e+01  2.87e-03  8.79e+01  8.79e+01      1  3.22e+03
  49  8.20e+02  8.79e+01  2.46e+01  2.65e-03  8.79e+01  8.79e+01      1  3.22e+03
---------------------------------------------------------------------------------
BPDN standard FISTA backtracking solve time: 0.05s

Plot comparison of reference and recovered representations.

plot.plot(np.hstack((x0, x)), title='Sparse representation (standard FISTA)',
          lgnd=['Reference', 'Reconstructed'])
../../_images/bpdn_fista_9_0.png

Plot lmbda error curve, functional value, residuals, and rho

its = b.getitstat()
fig = plot.figure(figsize=(21, 7))
plot.subplot(1, 3, 1)
plot.plot(its.ObjFun, xlbl='Iterations', ylbl='Functional', fig=fig)
plot.subplot(1, 3, 2)
plot.plot(its.Rsdl, ptyp='semilogy', xlbl='Iterations', ylbl='Residual',
          fig=fig)
plot.subplot(1, 3, 3)
plot.plot(its.L, xlbl='Iterations',
          ylbl='Inverse of Step Size (Standard FISTA)', fig=fig)
fig.show()
../../_images/bpdn_fista_11_0.png

Repeat for BPDN solver with robust FISTA backtracking.

opt = bpdn.BPDN.Options({'Verbose': True, 'MaxMainIter': 50,
            'BackTrack': {'Enabled': True, 'Robust' : True }, 'L': L_sc})


b = bpdn.BPDN(D, s, lmbda, opt)
x = b.solve()

print("BPDN robust FISTA backtracking solve time: %.2fs" %
      b.timer.elapsed('solve'))
Itn   Fnc       DFid      Regℓ1     Rsdl      F         Q         It_Bt  L
---------------------------------------------------------------------------------
   0  2.99e+03  1.33e+03  5.56e+01  1.87e+00  1.33e+03  1.57e+03      8  2.90e+03
   1  2.35e+03  7.11e+02  5.50e+01  2.06e+00  7.11e+02  8.40e+02      1  2.61e+03
   2  2.08e+03  3.74e+02  5.74e+01  8.90e-01  3.74e+02  3.94e+02      1  2.35e+03
   3  1.90e+03  3.37e+02  5.24e+01  6.42e-01  3.37e+02  3.42e+02      1  2.12e+03
   4  1.76e+03  2.29e+02  5.13e+01  5.65e-01  2.29e+02  2.35e+02      2  2.29e+03
   5  1.63e+03  2.43e+02  4.66e+01  5.40e-01  2.43e+02  2.55e+02      1  2.06e+03
   6  1.51e+03  1.90e+02  4.44e+01  5.55e-01  1.90e+02  2.00e+02      1  1.85e+03
   7  1.40e+03  2.06e+02  4.01e+01  5.76e-01  2.06e+02  2.17e+02      1  1.67e+03
   8  1.29e+03  1.58e+02  3.81e+01  6.07e-01  1.58e+02  1.64e+02      1  1.50e+03
   9  1.19e+03  1.85e+02  3.37e+01  6.34e-01  1.85e+02  1.89e+02      1  1.35e+03
  10  1.10e+03  1.27e+02  3.27e+01  6.13e-01  1.27e+02  1.28e+02      2  1.46e+03
  11  1.02e+03  1.57e+02  2.88e+01  6.12e-01  1.57e+02  1.60e+02      1  1.31e+03
  12  9.47e+02  1.10e+02  2.81e+01  5.85e-01  1.10e+02  1.13e+02      2  1.42e+03
  13  8.85e+02  1.20e+02  2.57e+01  5.70e-01  1.20e+02  1.27e+02      1  1.27e+03
  14  8.44e+02  8.79e+01  2.54e+01  5.34e-01  8.79e+01  8.95e+01      1  1.15e+03
  15  8.24e+02  8.79e+01  2.47e+01  4.57e-01  8.79e+01  9.47e+01      1  1.03e+03
  16  8.25e+02  7.58e+01  2.51e+01  3.07e-01  7.58e+01  8.06e+01      1  9.29e+02
  17  8.25e+02  7.88e+01  2.51e+01  1.98e-01  7.88e+01  8.51e+01      1  8.36e+02
  18  8.22e+02  7.99e+01  2.49e+01  2.24e-01  7.99e+01  8.18e+01      1  7.53e+02
  19  8.20e+02  8.85e+01  2.46e+01  1.78e-01  8.85e+01  8.87e+01      1  6.77e+02
  20  8.20e+02  8.86e+01  2.45e+01  1.01e-01  8.86e+01  8.86e+01      4  1.05e+03
  21  8.20e+02  9.00e+01  2.45e+01  5.68e-02  9.00e+01  9.00e+01      1  9.48e+02
  22  8.20e+02  8.93e+01  2.45e+01  3.55e-02  8.93e+01  8.94e+01      1  8.53e+02
  23  8.20e+02  8.95e+01  2.45e+01  2.96e-02  8.95e+01  8.95e+01      1  7.68e+02
  24  8.19e+02  8.86e+01  2.45e+01  3.03e-02  8.86e+01  8.86e+01      1  6.91e+02
  25  8.19e+02  8.93e+01  2.45e+01  2.72e-02  8.93e+01  8.93e+01      1  6.22e+02
  26  8.19e+02  8.85e+01  2.45e+01  1.80e-02  8.85e+01  8.85e+01      4  9.68e+02
  27  8.19e+02  8.86e+01  2.45e+01  1.15e-02  8.86e+01  8.86e+01      1  8.71e+02
  28  8.19e+02  8.83e+01  2.45e+01  7.75e-03  8.83e+01  8.83e+01      1  7.84e+02
  29  8.19e+02  8.86e+01  2.45e+01  6.87e-03  8.86e+01  8.86e+01      1  7.05e+02
  30  8.19e+02  8.84e+01  2.45e+01  6.55e-03  8.84e+01  8.84e+01      2  7.62e+02
  31  8.19e+02  8.85e+01  2.45e+01  5.00e-03  8.85e+01  8.85e+01      3  9.87e+02
  32  8.19e+02  8.85e+01  2.45e+01  3.77e-03  8.85e+01  8.85e+01      1  8.89e+02
  33  8.19e+02  8.86e+01  2.45e+01  2.79e-03  8.86e+01  8.86e+01      1  8.00e+02
  34  8.19e+02  8.86e+01  2.45e+01  2.11e-03  8.86e+01  8.86e+01      1  7.20e+02
  35  8.19e+02  8.86e+01  2.45e+01  1.84e-03  8.86e+01  8.86e+01      1  6.48e+02
  36  8.19e+02  8.86e+01  2.45e+01  1.66e-03  8.86e+01  8.86e+01      2  7.00e+02
  37  8.19e+02  8.86e+01  2.45e+01  1.27e-03  8.86e+01  8.86e+01      3  9.07e+02
  38  8.19e+02  8.86e+01  2.45e+01  9.95e-04  8.86e+01  8.86e+01      1  8.16e+02
---------------------------------------------------------------------------------
BPDN robust FISTA backtracking solve time: 0.05s

Plot comparison of reference and recovered representations.

plot.plot(np.hstack((x0, x)), title='Sparse representation (robust FISTA)',
          lgnd=['Reference', 'Reconstructed'])
../../_images/bpdn_fista_15_0.png

Plot lmbda error curve, functional value, residuals, and rho

its = b.getitstat()
fig = plot.figure(figsize=(21, 7))
plot.subplot(1, 3, 1)
plot.plot(its.ObjFun, xlbl='Iterations', ylbl='Functional', fig=fig)
plot.subplot(1, 3, 2)
plot.plot(its.Rsdl, ptyp='semilogy', xlbl='Iterations', ylbl='Residual',
          fig=fig)
plot.subplot(1, 3, 3)
plot.plot(its.L, xlbl='Iterations',
          ylbl='Inverse of Step Size (robust FISTA)', fig=fig)
fig.show()
../../_images/bpdn_fista_17_0.png