magni.cs.reconstruction.it._algorithm module

Module providing the core Iterative Thresholding (IT) algorithm.

Routine listings

run(y, A)

Run the IT reconstruction algorithm.

See also

magni.cs.reconstruction.it._config

Configuration options.

magni.cs.reconstruction.it._step_size

Available step-size strategies.

magni.cs.reconstruction.it._stop_criterion

Available stop criteria.

magni.cs.reconstruction.it._threshold

Available threshold estimators.

magni.cs.reconstruction.it._threshold_operators

Available threshold operators

Notes

The default configuration of the IT algorithm provides the Iterative Hard Thresholding (IHT) algorithm [1] using the False Alarm Rate (FAR) heuristic from [2]. By default a residual measurements ratio step criterion is used. The algorithm may also be configured to act as the Iterative Soft Thresholding (IST) [3] algorithm with the soft threshold from [4].

References

[1]	T. Blumensath and M.E. Davies, “Iterative Thresholding for Sparse Approximations”, Journal of Fourier Analysis and Applications, vol. 14, pp. 629-654, Sep. 2008.

[2]	A. Maleki and D.L. Donoho, “Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing”, IEEE Journal Selected Topics in Signal Processing, vol. 3, no. 2, pp. 330-341, Apr. 2010.

[3]	I. Daubechies, M. Defrise, and C. D. Mol, “An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint”, Communications on Pure and Applied Mathematics, vol. 57, no. 11, pp. 1413-1457, Nov. 2004.

[4]	D.L. Donoho, “De-Noising by Soft-Thresholding”, IEEE Transactions on Information Theory, vol. 41, no. 3, pp. 613-627, May. 1995.

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

Run the IT 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.
• history (dict, optional) – The dictionary of various measures tracked in the IT iterations.

See also

magni.cs.reconstruction.it._config()

Configuration options.

magni.cs.reconstruction.it._step_size()

Step-size calculation.

magni.cs.reconstruction.it._stop_criterion()

Stop criterion calculation.

magni.cs.reconstruction.it._threshold()

Threshold calculation.

magni.cs.reconstruction.it._threshold_operators()

Thresholding operators.

Notes

Optionally, the algorithm may be configured to save and return the iteration history along with the reconstruction result. The returned history contains the following:

• alpha : Reconstruction coefficient estimates
• MSE : Solution mean squared error (if the true solution is known).
• stop_criterion : The currently used stop criterion.
• stop_criterion_value : The value of the stop criterion.
• stop_iteration : The iteration at which the algorithm stopped.
• stop_reason : The reason for termination of the algorithm.

Examples

For example, recovering a vector from random measurements using IHT with the FAR heuristic

>>> import numpy as np, magni
>>> from magni.cs.reconstruction.it import run
>>> np.random.seed(seed=6021)
>>> A = 1 / np.sqrt(90) * np.random.randn(90, 200)
>>> alpha = np.zeros((200, 1))
>>> alpha[:10] = 1
>>> y = A.dot(alpha)
>>> alpha_hat = run(y, A)
>>> alpha_hat[:12]
array([[ 0.99748945],
       [ 1.00082074],
       [ 0.99726507],
       [ 0.99987834],
       [ 1.00025857],
       [ 1.00003266],
       [ 1.00021666],
       [ 0.99838884],
       [ 1.00018356],
       [ 0.99859105],
       [ 0.        ],
       [ 0.        ]])
>>> (np.abs(alpha_hat) > 1e-2).sum()
10

Or recover the same vector as above using IST with a fixed number of non-thresholded coefficients

>>> it_config = {'threshold_operator': 'soft', 'threshold': 'fixed',
... 'threshold_fixed': 10}
>>> magni.cs.reconstruction.it.config.update(it_config)
>>> alpha_hat = run(y, A)
>>> alpha_hat[:12]
array([[ 0.99822443],
       [ 0.99888724],
       [ 0.9982493 ],
       [ 0.99928642],
       [ 0.99964131],
       [ 0.99947346],
       [ 0.9992809 ],
       [ 0.99872624],
       [ 0.99916842],
       [ 0.99903033],
       [ 0.        ],
       [ 0.        ]])
>>> (np.abs(alpha_hat) > 1e-2).sum()
10

Or use a weighted IHT method with a fixed number of non-thresholded coefficietns to recover the above signal

>>> weights = np.linspace(1.0, 0.9, 200).reshape(200, 1)
>>> it_config = {'threshold_operator': 'weighted_hard',
... 'threshold_weights': weights}
>>> magni.cs.reconstruction.it.config.update(it_config)
>>> alpha_hat = run(y, A)
>>> alpha_hat[:12]
array([[ 0.99853888],
       [ 0.99886104],
       [ 0.99843149],
       [ 1.0000333 ],
       [ 1.00060273],
       [ 1.00035539],
       [ 0.99966219],
       [ 0.99912209],
       [ 0.99961541],
       [ 0.99952029],
       [ 0.        ],
       [ 0.        ]])
>>> (np.abs(alpha_hat) > 1e-2).sum()
10
>>> magni.cs.reconstruction.it.config.reset()