linear_operators

about install code documentation exemples contact

Introduction

linear_operators is a package implementing estimation algorithms for large scale linear inverse problems. This class of problem includes deconvolution or tomography for instance.

Workflow

• generate a linear model using LinearOperator instances as buildling blocks,
• define a criterion to minimize using this model (e.g. least-square),
• finally, perform minimization on the criterion using a minimization algorithm (e.g. conjugate gradient).

Design

In its most simple form, linear inverse estimation simply consists in find the variable $$x$$ knowing the equation $$y = A x$$, the data y and the linear model (or matrix) $$A$$. As large scale problems can scale to millions of data element and unknowns, inverting the matrix $$A$$ or even storing it is impossible. Fortunately, $$x$$ can be found with algorithms which require only to perform the matrix vector operations $$A x$$ and $$A^T y$$. The LinearOperator object is an object which stores precisely those operations and mimics the behavior of a standard matrix to a given extent. For instance, it is possible to add or multiply LinearOperators.

It can be shown that inverting the equation $$y = A x$$ can be done by minimizing the cost function $$\| y - Ax \|^2$$ with respect to $$x$$ (this is for instance the method of least squares. Using LinearOperators it is possible to define cost functions (also called criterions) whose minimum correspond to a least squares solution.

These criterions can then be passed to minimization algorithms which handle functions as arguments, as do the optimizers provided by the scipy.optimize package.

The linear_operators package provide a set of standard LinearOperators subclasses such as convolution, Fourier transform, wavelets, ... It also provides a set of minimization algorithms and bindings to scipy.optimize optimizers and also scikits.optimization.

Other packages can define their own linear_operators instances. This is the case of the TomograPy package. Python objects having a shape attribute and a matvec method can also be recasted as LinearOperators.

Subpackages

• interface : Taken from the scipy.sparse package. It implement the LinearOperator class which replaces matrices and do not require to store any matrix coefficient. It makes use of matrix-vector operations instead.
• operators : A set of LinearOperator subclasses implementing various linear operation on vectors and their transpose.
• ndoperators : A set of LinearOperator subclasses implementing operations on multidimensional arrays.
• iterative : Contains the Criterion class which allows to define objective function as well as minimizers such as the conjugate gradient algorithms and wrappers to other minimizing algorithms.
• wrappers : define extra LinearOperator subclasses if optional dependencies are available.