code.rst 16.3 KB
Newer Older
Philipp Arras's avatar
Philipp Arras committed
1
.. currentmodule:: nifty5
2

Martin Reinecke's avatar
Martin Reinecke committed
3
=============
4 5
Code Overview
=============
6

Martin Reinecke's avatar
Martin Reinecke committed
7 8 9 10

Executive summary
=================

11 12
The fundamental building blocks required for IFT computations are best
recognized from a large distance, ignoring all technical details.
13

14 15
From such a perspective,

16 17 18 19
- IFT problems largely consist of the combination of several high dimensional 
  *minimization* problems.
- Within NIFTy, *models* are used to define the characteristic equations and  
  properties of the problems. 
Martin Reinecke's avatar
Martin Reinecke committed
20 21
- The equations are built mostly from the application of *linear operators*,
  but there may also be nonlinear functions involved.
22
- The unknowns in the equations represent either continuous physical *fields*,
Martin Reinecke's avatar
Martin Reinecke committed
23 24 25 26
  or they are simply individual measured *data points*.
- Discretized *fields* have geometrical information (like locations and volume
  elements) associated with every entry; this information is called the field's
  *domain*.
27 28 29 30 31 32 33 34 35 36 37 38 39

In the following sections, the concepts briefly presented here will be
discussed in more detail; this is done in reversed order of their introduction,
to avoid forward references.


Domains
=======


Abstract base class
-------------------

Philipp Arras's avatar
Philipp Arras committed
40
One of the fundamental building blocks of the NIFTy5 framework is the *domain*.
41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
Its required capabilities are expressed by the abstract :class:`Domain` class.
A domain must be able to answer the following queries:

- its total number of data entries (pixels), which is accessible via the
  :attr:`~Domain.size` property
- the shape of the array that is supposed to hold these data entries
  (obtainable by means of the :attr:`~Domain.shape` property)
- equality comparison to another :class:`Domain` instance


Unstructured domains
--------------------

Domains can be either *structured* (i.e. there is geometrical information
associated with them, like position in space and volume factors),
or *unstructured* (meaning that the data points have no associated manifold).

Unstructured domains can be described by instances of NIFTy's
:class:`UnstructuredDomain` class.


Structured domains
------------------

In contrast to unstructured domains, these domains have an assigned geometry.
NIFTy requires them to provide the volume elements of their grid cells.
The additional methods are specified in the abstract class
:class:`StructuredDomain`:

Martin Reinecke's avatar
Martin Reinecke committed
70
- The properties :attr:`~StructuredDomain.scalar_dvol`,
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
  :attr:`~StructuredDomain.dvol`, and  :attr:`~StructuredDomain.total_volume`
  provide information about the domain's pixel volume(s) and its total volume.
- The property :attr:`~StructuredDomain.harmonic` specifies whether a domain
  is harmonic (i.e. describes a frequency space) or not
- Iff the domain is harmonic, the methods
  :meth:`~StructuredDomain.get_k_length_array`,
  :meth:`~StructuredDomain.get_unique_k_lengths`, and
  :meth:`~StructuredDomain.get_fft_smoothing_kernel_function` provide absolute
  distances of the individual grid cells from the origin and assist with
  Gaussian convolution.

NIFTy comes with several concrete subclasses of :class:`StructuredDomain`:

- :class:`RGSpace` represents a regular Cartesian grid with an arbitrary
  number of dimensions, which is supposed to be periodic in each dimension.
- :class:`HPSpace` and :class:`GLSpace` describe pixelisations of the
  2-sphere; their counterpart in harmonic space is :class:`LMSpace`, which
  contains spherical harmonic coefficients.
- :class:`PowerSpace` is used to describe one-dimensional power spectra.

Among these, :class:`RGSpace` can be harmonic or not (depending on constructor arguments), :class:`GLSpace`, :class:`HPSpace`, and :class:`PowerSpace` are
pure position domains (i.e. nonharmonic), and :class:`LMSpace` is always
harmonic.


Combinations of domains
=======================

The fundamental classes described above are often sufficient to specify the
domain of a field. In some cases, however, it will be necessary to have the
field live on a product of elementary domains instead of a single one.
Some examples are:

- sky emission depending on location and energy. This could be represented by
  a product of an :class:`HPSpace` (for location) with an :class:`RGSpace`
  (for energy).
- a polarised field, which could be modeled as a product of any structured
Martin Reinecke's avatar
Martin Reinecke committed
108 109
  domain (representing location) with a four-element
  :class:`UnstructuredDomain` holding Stokes I, Q, U and V components.
110 111 112 113 114 115

Consequently, NIFTy defines a class called :class:`DomainTuple` holding
a sequence of :class:`Domain` objects, which is used to specify full field
domains. In principle, a :class:`DomainTuple` can even be empty, which implies
that the field living on it is a scalar.

Martin Reinecke's avatar
Martin Reinecke committed
116 117 118 119
A :class:`DomainTuple` supports iteration and indexing, and also provides the
properties :attr:`~DomainTuple.shape`, :attr:`~DomainTuple.size` in analogy to
the elementary :class:`Domain`.

120 121 122 123 124 125 126 127 128 129

Fields
======

A :class:`Field` object consists of the following components:

- a domain in form of a :class:`DomainTuple` object
- a data type (e.g. numpy.float64)
- an array containing the actual values

Martin Reinecke's avatar
Martin Reinecke committed
130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151
Usually, the array is stored in the for of a ``numpy.ndarray``, but for very
resource-intensive tasks NIFTy also provides an alternative storage method to
be used with distributed memory processing.

Fields support a wide range of arithmetic operations, either involving two
fields with equal domains, or a field and a scalar.
Contractions (like summation, integration, minimum/maximum, computation of
statistical moments) can be carried out either over an entire field (producing
a scalar result) or over sub-domains (resulting in a field living on a smaller
domain). Scalar products of two fields can also be computed easily.

There is also a set of convenience functions to generate fields with constant
values or fields filled with random numbers according to a user-specified
distribution.

Fields are the only fundamental NIFTy objects which can change state after they
have been constructed: while their data type, domain, and array shape cannot
be modified, the actual data content of the array may be manipulated during the
lifetime of the object. This is a slight deviation from the philosophy that all
NIFTy objects should be immutable, but this choice offers considerable
performance benefits.

152 153 154 155

Linear Operators
================

Philipp Arras's avatar
Philipp Arras committed
156
A linear operator (represented by NIFTy5's abstract :class:`LinearOperator`
157 158 159 160
class) can be interpreted as an (implicitly defined) matrix.
It can be applied to :class:`Field` instances, resulting in other :class:`Field`
instances that potentially live on other domains.

Martin Reinecke's avatar
Martin Reinecke committed
161 162 163 164

Operator basics
---------------

165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
There are four basic ways of applying an operator :math:`A` to a field :math:`f`:

- direct multiplication: :math:`A\cdot f`
- adjoint multiplication: :math:`A^\dagger \cdot f`
- inverse multiplication: :math:`A^{-1}\cdot f`
- adjoint inverse multiplication: :math:`(A^\dagger)^{-1}\cdot f`

(For linear operators, inverse adjoint multiplication and adjoint inverse
multiplication are equivalent.)

These different actions of an operator ``Op`` on a field ``f`` can be invoked
in various ways:

- direct multiplication: ``Op(f)`` or ``Op.times(f)`` or ``Op.apply(f, Op.TIMES)``
- adjoint multiplication: ``Op.adjoint_times(f)`` or ``Op.apply(f, Op.ADJOINT_TIMES)``
- inverse multiplication: ``Op.inverse_times(f)`` or ``Op.apply(f, Op.INVERSE_TIMES)``
- adjoint inverse multiplication: ``Op.adjoint_inverse_times(f)`` or ``Op.apply(f, Op.ADJOINT_INVERSE_TIMES)``

Operator classes defined in NIFTy may implement an arbitrary subset of these
four operations. This subset can be queried using the
:attr:`~LinearOperator.capability` property.

If needed, the set of supported operations can be enhanced by iterative
inversion methods;
for example, an operator defining direct and adjoint multiplication could be
Martin Reinecke's avatar
Martin Reinecke committed
190
enhanced by this approach to support the complete set. This functionality is
191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
provided by NIFTy's :class:`InversionEnabler` class, which is itself a linear
operator.

There are two :class:`DomainTuple` objects associated with a
:class:`LinearOperator`: a :attr:`~LinearOperator.domain` and a
:attr:`~LinearOperator.target`.
Direct multiplication and adjoint inverse multiplication transform a field
living on the operator's :attr:`~LinearOperator.domain` to one living on the operator's :attr:`~LinearOperator.target`, whereas adjoint multiplication
and inverse multiplication transform from :attr:`~LinearOperator.target` to :attr:`~LinearOperator.domain`.

Operators with identical domain and target can be derived from
:class:`EndomorphicOperator`; typical examples for this category are the :class:`ScalingOperator`, which simply multiplies its input by a scalar
value, and :class:`DiagonalOperator`, which multiplies every value of its input
field with potentially different values.

Further operator classes provided by NIFTy are

Martin Reinecke's avatar
Martin Reinecke committed
208 209
- :class:`HarmonicTransformOperator` for transforms from a harmonic domain to
  its counterpart in position space, and their adjoint
210
- :class:`PowerDistributor` for transforms from a :class:`PowerSpace` to
Martin Reinecke's avatar
Martin Reinecke committed
211
  an associated harmonic domain, and their adjoint
212 213 214 215
- :class:`GeometryRemover`, which transforms from structured domains to
  unstructured ones. This is typically needed when building instrument response
  operators.

Martin Reinecke's avatar
Martin Reinecke committed
216

Martin Reinecke's avatar
Martin Reinecke committed
217 218
Syntactic sugar
---------------
Martin Reinecke's avatar
Martin Reinecke committed
219

Martin Reinecke's avatar
Martin Reinecke committed
220
Nifty5 allows simple and intuitive construction of altered and combined
221 222
operators.
As an example, if ``A``, ``B`` and ``C`` are of type :class:`LinearOperator`
Martin Reinecke's avatar
Martin Reinecke committed
223
and ``f1`` and ``f2`` are of type :class:`Field`, writing::
224 225 226 227 228 229 230 231 232 233 234 235 236

    X = A*B.inverse*A.adjoint + C
    f2 = X(f1)

will perform the operation suggested intuitively by the notation, checking
domain compatibility while building the composed operator.
The combined operator infers its domain and target from its constituents,
as well as the set of operations it can support.
The properties :attr:`~LinearOperator.adjoint` and
:attr:`~LinearOperator.inverse` return a new operator which behaves as if it
were the original operator's adjoint or inverse, respectively.


237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290
Models
======

Model classes (represented by NIFTy5's abstract :class:`Model` class) are used to construct
the equations of a specific inference problem. 
Most models are defined via a position, which is a :class:`MultiField` object,  
their value at these positions, which is again a :class:`MultiField` object and a jacobian derivative, 
which is a :class:`LinearOperator` and is needed for the minimization procedure.
Using the existing basic model classes one can construct more complicated models, as
NIFTy allows for easy and self-consinstent combination via pointwise multiplication, 
addition and subtraction. The resulting model of these operations then automatically 
contains the correct jacobians, positions and values. 
Notably, :class:`Constant` and :class:`Variable` allows for an easy way to turn on and off the 
inference of specific quantities.
The basic model classes also allow for more complex operations on models such as 
the application of :class:`LinearOperators` or local non-linearities.
As an example one may consider the following combination of ``x``, which is a model of type
:class:`Variable` and ``y``, which is a model of type :class:`Constant`::

	z = x*x + y 

``z`` will then be a model with position::

	z.value = x.value*x.value + y.value
	z.position = x.position*x.position + y.position
	z.jacobian = 2*makeOp(x.value)


Basic models
------------ 

Basic model classes provided by NIFTy are 

- :class:`Constant` contains a constant value and has a zero valued jacobian. 
It has no position (?currently it still has one?), as the value is the same everywhere.
- :class:`Variable` returns the position as its value, its derivative is one.
- :class:`LinearModel` applies a :class:`LinearOperator` on the model.
- :class:`LocalModel` applies a non-linearity locally on the model.
- :class:`MultiModel` combines various models into one. In this case the position, 
	value and jacobian get combined into corresponding :class:`MultiFields` and operators.  
 

Advanced models
---------------

NIFTy also provides a library of more sophisticated models which are used for more 
specific inference problems. Currently these are:

- :class:'AmplitudeModel', which returns a smooth power spectrum. 
- :class:'PointModel', which models points sources which follow a inverse gamma distribution.
- :class:'SmoothSkyModel', which models a diffuse lognormal field. It takes an amplitude model
	to specify the correlation structure of the field.


291 292
.. _minimization:

Martin Reinecke's avatar
Martin Reinecke committed
293

294 295 296
Minimization
============

Martin Reinecke's avatar
Martin Reinecke committed
297 298 299 300 301 302
Most problems in IFT are solved by (possibly nested) minimizations of
high-dimensional functions, which are often nonlinear.


Energy functionals
------------------
303

Philipp Arras's avatar
Philipp Arras committed
304
In NIFTy5 such functions are represented by objects of type :class:`Energy`.
Martin Reinecke's avatar
Martin Reinecke committed
305 306
These hold the prescription how to calculate the function's
:attr:`~Energy.value`, :attr:`~Energy.gradient` and
Martin Reinecke's avatar
Martin Reinecke committed
307 308
(optionally) :attr:`~Energy.curvature` at any given :attr:`~Energy.position`
in parameter space.
Martin Reinecke's avatar
Martin Reinecke committed
309 310 311
Function values are floating-point scalars, gradients have the form of fields
living on the energy's position domain, and curvatures are represented by
linear operator objects.
312

Martin Reinecke's avatar
Martin Reinecke committed
313 314
Energies are classes that typically have to be provided by the user when
tackling new IFT problems.
Philipp Arras's avatar
Philipp Arras committed
315
Some examples of concrete energy classes delivered with NIFTy5 are
Martin Reinecke's avatar
Martin Reinecke committed
316
:class:`QuadraticEnergy` (with position-independent curvature, mainly used with
Philipp Arras's avatar
Philipp Arras committed
317
conjugate gradient minimization) and :class:`~nifty5.library.WienerFilterEnergy`.
318

Martin Reinecke's avatar
Martin Reinecke committed
319 320 321

Iteration control
-----------------
Martin Reinecke's avatar
Martin Reinecke committed
322 323

Iterative minimization of an energy reqires some means of
Martin Reinecke's avatar
Martin Reinecke committed
324
checking the quality of the current solution estimate and stopping once
Martin Reinecke's avatar
Martin Reinecke committed
325 326 327
it is sufficiently accurate. In case of numerical problems, the iteration needs
to be terminated as well, returning a suitable error description.

Philipp Arras's avatar
Philipp Arras committed
328
In NIFTy5, this functionality is encapsulated in the abstract
Martin Reinecke's avatar
Martin Reinecke committed
329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344
:class:`IterationController` class, which is provided with the initial energy
object before starting the minimization, and is updated with the improved
energy after every iteration. Based on this information, it can either continue
the minimization or return the current estimate indicating convergence or
failure.

Sensible stopping criteria can vary significantly with the problem being
solved; NIFTy provides one concrete sub-class of :class:`IterationController`
called :class:`GradientNormController`, which should be appropriate in many
circumstances, but users have complete freedom to implement custom sub-classes
for their specific applications.


Minimization algorithms
-----------------------

Martin Reinecke's avatar
Martin Reinecke committed
345 346 347 348 349 350 351 352 353 354 355 356 357
All minimization algorithms in NIFTy inherit from the abstract
:class:`Minimizer` class, which presents a minimalistic interface consisting
only of a :meth:`~Minimizer.__call__` method taking an :class:`Energy` object
and optionally a preconditioning operator, and returning the energy at the
discovered minimum and a status code.

For energies with a quadratic form (i.e. which
can be expressed by means of a :class:`QuadraticEnergy` object), an obvious
choice of algorithm is the :class:`ConjugateGradient` minimizer.

A similar algorithm suited for nonlinear problems is provided by
:class:`NonlinearCG`.

Martin Reinecke's avatar
Martin Reinecke committed
358
Many minimizers for nonlinear problems can be characterized as
Martin Reinecke's avatar
Martin Reinecke committed
359 360 361 362 363 364 365 366 367 368 369 370

- first deciding on a direction for the next step
- then finding a suitable step length along this direction, resulting in the
  next energy estimate.

This family of algorithms is encapsulated in NIFTy's :class:`DescentMinimizer`
class, which currently has three concrete implementations:
:class:`SteepestDescent`, :class:`VL_BFGS`, and :class:`RelaxedNewton`.
Of these algorithms, only :class:`RelaxedNewton` requires the energy object to
provide a :attr:`~Energy.curvature` property, the others only need energy
values and gradients.

Martin Reinecke's avatar
Martin Reinecke committed
371 372 373 374 375
The flexibility of NIFTy's design allows using externally provided
minimizers. With only small effort, adapters for two SciPy minimizers were
written; they are available under the names :class:`NewtonCG` and
:class:`L_BFGS_B`.

Martin Reinecke's avatar
Martin Reinecke committed
376 377 378 379

Application to operator inversion
---------------------------------

Martin Reinecke's avatar
Martin Reinecke committed
380 381 382 383 384 385 386 387 388 389
It is important to realize that the machinery presented here cannot only be
used for minimizing IFT Hamiltonians, but also for the numerical inversion of
linear operators, if the desired application mode is not directly available.
A classical example is the information propagator

:math:`D = \left(R^\dagger N^{-1} R + S^{-1}\right)^{-1}`,

which must be applied when calculating a Wiener filter. Only its inverse
application is straightforward; to use it in forward direction, we make use
of NIFTy's :class:`InversionEnabler` class, which internally performs a
Martin Reinecke's avatar
Martin Reinecke committed
390
minimization of a :class:`QuadraticEnergy` by means of the
Martin Reinecke's avatar
Martin Reinecke committed
391
:class:`ConjugateGradient` algorithm.