magni.cs.reconstruction.sl0._algorithm module

Module providing the core Smoothed l0 (SL0) algorithm.

Routine listings

run(y, A)

Run the SL0 reconstruction algoritm.

See also

magni.cs.reconstruction.sl0._config

Configuration options.

Notes

Implementations of the original SL0 reconstruction algorithm [1] and a modified Sl0 reconstruction algorithm [3] are available. It is also possible to configure the subpackage to provide customised versions of the SL0 reconstruction algorithm. The projection algorithm [1] is used for small delta (< 0.55) whereas the contraint elimination algorithm [2] is used for large delta (>= 0.55) which merely affects the computation time.

References

[1]	(1, 2) H. Mohimani, M. Babaie-Zadeh, and C. Jutten, “A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed l0 Norm”, IEEE Transactions on Signal Processing, vol. 57, no. 1, pp. 289-301, Jan. 2009.

[2]	Z. Cui, H. Zhang, and W. Lu, “An Improved Smoothed l0-norm Algorithm Based on Multiparameter Approximation Function”, in 12th IEEE International Conference on Communication Technology (ICCT), Nanjing, China, Nov. 11-14, 2011, pp. 942-945.

[3]

C. S. Oxvig, P. S. Pedersen, T. Arildsen, and T. Larsen, “Surpassing the Theoretical 1-norm Phase Transition in Compressive Sensing by Tuning the Smoothed l0 Algorithm”, in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Vancouver, Canada, May 26-31, 2013, pp. 6019-6023.

magni.cs.reconstruction.sl0._algorithm.run(y, A)

Run the SL0 reconstruction algorithm.

Parameters:

• y (ndarray) – The m x 1 measurement vector.
• A (ndarray or magni.utils.matrices.{Matrix, MatrixCollection}) – The m x n matrix which is the product of the measurement matrix and the dictionary matrix.

Returns:

alpha (ndarray) – The n x 1 reconstructed coefficient vector.

See also

magni.cs.reconstruction.sl0.config()

Configuration options.

Notes

The algorithm terminates after a fixed number of iterations or if the ratio between the 2-norm of the residual and the 2-norm of the measurements falls below the specified tolerance.

Examples

For example, recovering a vector from random measurements using the original SL0 reconstruction algorithm

>>> import numpy as np, magni
>>> from magni.cs.reconstruction.sl0 import run
>>> np.set_printoptions(suppress=True)
>>> magni.cs.reconstruction.sl0.config['L'] = 'fixed'
>>> magni.cs.reconstruction.sl0.config['mu'] = 'fixed'
>>> magni.cs.reconstruction.sl0.config['sigma_start'] = 'fixed'
>>> np.random.seed(seed=6021)
>>> A = 1 / np.sqrt(80) * np.random.randn(80, 200)
>>> alpha = np.zeros((200, 1))
>>> alpha[:10] = 1
>>> y = A.dot(alpha)
>>> alpha_hat = run(y, A)
>>> alpha_hat[:12]
array([[ 0.99993202],
       [ 0.99992793],
       [ 0.99998107],
       [ 0.99998105],
       [ 1.00005882],
       [ 1.00000843],
       [ 0.99999138],
       [ 1.00009479],
       [ 0.99995889],
       [ 0.99992509],
       [-0.00001509],
       [ 0.00000275]])
>>> (np.abs(alpha_hat) > 1e-2).sum()
10

Or recover the same vector as above using the modified SL0 reconstruction algorithm

>>> magni.cs.reconstruction.sl0.config['L'] = 'geometric'
>>> magni.cs.reconstruction.sl0.config['mu'] = 'step'
>>> magni.cs.reconstruction.sl0.config['sigma_start'] = 'reciprocal'
>>> alpha_hat = run(y, A)
>>> alpha_hat[:12]
array([[ 0.9999963 ],
       [ 1.00000119],
       [ 1.00000293],
       [ 0.99999661],
       [ 1.00000021],
       [ 0.9999951 ],
       [ 1.00000103],
       [ 1.00000662],
       [ 1.00000404],
       [ 0.99998937],
       [-0.00000075],
       [ 0.00000037]])
>>> (np.abs(alpha_hat) > 1e-2).sum()
10