Camiba – Algorithms

This submodule aims at providing a rich ensemble of algorithms, which are implementend with easy to read code and not many optimizations for rapid prototyping and adaption for own more specifically tailored applications.

ADMM

This module provides different specialiced implementations of the well known method of alternating direction multipliers [ADMM]. Since the method is so general, many variants exist and many optimizations problems can be recast into a problem, which can be solved by a specific ADMM.

camiba.algs.admm.anm_lse_1d(A, AH, AHA, y, rho, tau, num_steps)[source]

Atomic Norm Denoising for 1D Line Spectral Estimation

This ADMM approximates a solution to

min_[x,u,t] 1/(2n) trace T(u) + 1/2 t s.t. [[T(u), x], [x^H, t]] >= 0, ||b - Ax||_2 < z

for given matrix A, vector b and z > 0. Moreover, T(u) maps the vector u to a Hermitian Toeplitz matrix defined by u.

Parameters:

A : ndarray

system matrix

AH : ndarray

Hermitian transpose of system matrix

AHA : ndarray

Gram matrix of system matrix

b : ndarray

measurement vector

rho : float

parameter for augmented lagrangian

alpha : float

thresholding parameter

num_steps : int

number of steps
Returns:

(ndarray, ndarray, ndarray)

x, T(u), t
camiba.algs.admm.anm_lse_nd(A, AH, AHA, y, rho, tau, num_steps, arr_d)[source]

Atomic Norm Denoising for 1D Line Spectral Estimation

This ADMM approximates a solution to

min_[x,u,t] 1/(2n) trace T(u) + 1/2 t s.t. [[T(u), x], [x^H, t]] >= 0, ||b - Ax||_2 < z

for given matrix A, vector b and z > 0. Moreover, T(u) maps the tensor of order l u to a l-level Hermitian Toeplitz matrix defined by u.

Parameters:

A : ndarray

system matrix

AH : ndarray

Hermitian transpose of system matrix

AHA : ndarray

Gram matrix of system matrix

b : ndarray

measurement vector

rho : float

parameter for augmented lagrangian

alpha : float

thresholding parameter

num_steps : int

number of steps

arr_d : ndarray

dimension sizes
Returns:

(ndarray, ndarray, ndarray)

x, T(u), t
camiba.algs.admm.bpdn_1d(A, b, x_init, rho, alpha, num_steps)[source]

Basis Pursuit Denoising

For given matrix A, vector b and z > 0, ADDM approximates a solution to

min ||x||_1 s.t. ||A * x - b||_2 < z.

The algorithm needs a thresholding parameter, an initial guess for a solution and a parameter for the augmented lagrangian.

Parameters:

A : ndarray

system matrix

b : ndarray

measurement vector

x_init : ndarray

initial solution guess

rho : float

parameter for augmented lagrangian

alpha : float

thresholding parameter

num_steps : int

number of steps
Returns:

ndarray

approximated solution to BPDN

IHT

Provides the Iterative Hard Thresholding Algorithm to approximate a solution to the l_0-minimization problem, which reads as

min ||x||_0 s.t. Ax = b

for given matrix A and vector b and it is described and analyzed in [IHT].

camiba.algs.iht.recover(mat_A, arr_b, num_maxsteps, num_k)[source]
IHT Algorithm
Parameters:

mat_A : ndarray

system matrix

arr_b : ndarray

measurement vector

num_steps : int

iteration steps

num_k : int

thresholding parameter
Returns:

ndarray

estimated sparse solution

IRLS

Implements the algorithm of iteratively reweighted least squares for approximating a solution to a l_0-minimization problem, which reads as

min ||x||_0 s.t. Ax = b

for given matrix A and vector b and it is described and analyzed in [IRLS].

camiba.algs.irls.recover(mat_A, arr_b, num_eps, num_s, verbose=0)[source]
Iteratively Reweighted Least Squares
Parameters:

mat_A : ndarray

system matrix

arr_b : ndarray

measurement vector

num_eps : float

stopping criterion

num_steps : int

iteration steps
Returns:

ndarray

estimated sparse solution

ISTA

Implements the algorithm of iterative soft thresholding for approximating a solution to a l_1-minimization problem, which reads as

min ||x||_a + lambda * ||Ax - b||_2^2

for given matrix A and vector b and it is described and analyzed in [ISTA].

camiba.algs.ista.recover(mat_A, arr_b, x_init, num_lambda, num_steps)[source]
Iterative Soft Thresholding Algorithm
Parameters:

mat_A : ndarray

system matrix

arr_b : ndarray

measurement vector

x_init : ndarray

initial solution guess

num_lambda : int

thresholding parameter

num_steps : int

iteration steps
Returns:

ndarray

estimated sparse solution

OMP

Provides the Orthogonal Matching Pursuit Algorithm to approximate a solution to the l_0-minimization problem, which reads as

min ||x||_0 s.t. Ax = b

for given matrix A and vector b and it is described and analyzed in [OMP].

camiba.algs.omp.recover(mat_A, arr_b, num_steps)[source]
Orthogonal Matching Pursuit Algorithm
Parameters:

mat_A : ndarray

system matrix

arr_b : ndarray

measurement vector

num_steps : int

iteration steps
Returns:

ndarray

estimated sparse solution

References

[ADMM]Distributed optimization and statistical learning via the alternating direction method of multipliers S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, 2011
[IHT]Iterative Hard Thresholding for Compressed Sensing Thomas Blumensath, Mike E. Davies arXiv:0805.0510
[IRLS]Iteratively reweighted least squares minimization for sparse recovery Daubechies, I.; Devore, R.; Fornasier, M.; Güntürk Communications on Pure and Applied Mathematics
[ISTA]An iterative thresholding algorithm for linear inverse problems with a sparsity constraint Ingrid Daubechies (Princeton University, USA), Michel Defrise (Vrije Universiteit Brussel, Belgium), Christine De Mol (Universite Libre de Bruxelles, Belgium)
[OMP]Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition Y. C. Pati, R. Rezaiifar and P. S. Krishnaprasad Proceedings of 27th Asilomar Conference on Signals, Systems and Computers