code.rst 12.4 KB
Newer Older
1
.. currentmodule:: nifty4
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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
70
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
From such a perspective,

- IFT problems largely consist of *minimization* problems involving a large
  number of equations.
- The equations are built mostly from the application of *linear operators*, but
  there may also be nonlinear functions involved.
- The unknowns in the equations represent either continuous physical *fields*,
  or they are simply individual measured *data* points.
- The locations and volume elements attached to discretized *field* values are
  supplied by *domain* objects. There are many variants of such discretized
  *domains* supported by NIFTy4, including Cartesian and spherical geometries
  and their harmonic counterparts. *Fields* can live on arbitrary products of
  such *domains*.

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
-------------------

One of the fundamental building blocks of the NIFTy4 framework is the *domain*.
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`:

- The attributes :attr:`~StructuredDomain.scalar_dvol`,
  :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
  domain representing location with a four-element :class:`UnstructuredDomain`
  holding Stokes I, Q, U and V components.

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.


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

Fields support arithmetic operations, contractions, etc.

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

A linear operator (represented by NIFTy4's abstract :class:`LinearOperator`
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
136
137
138
139

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

140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
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
190
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
enhanced to support the complete set by this method. This functionality is
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

- :class:`HarmonicTransformOperator` for transforms from harmonic domain to
  their counterparts in position space, and their adjoint
- :class:`PowerDistributor` for transforms from a :class:`PowerSpace` to
  the associated harmonic domain, and their adjoint
- :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
191

Martin Reinecke's avatar
Martin Reinecke committed
192
193
Syntactic sugar
---------------
Martin Reinecke's avatar
Martin Reinecke committed
194

195
196
197
Nifty4 allows simple and intuitive construction of altered and combined
operators.
As an example, if ``A``, ``B`` and ``C`` are of type :class:`LinearOperator`
Martin Reinecke's avatar
Martin Reinecke committed
198
and ``f1`` and ``f2`` are of type :class:`Field`, writing::
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213

    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.


.. _minimization:

Martin Reinecke's avatar
Martin Reinecke committed
214

215
216
217
Minimization
============

Martin Reinecke's avatar
Martin Reinecke committed
218
219
220
221
222
223
Most problems in IFT are solved by (possibly nested) minimizations of
high-dimensional functions, which are often nonlinear.


Energy functionals
------------------
224
225

In NIFTy4 such functions are represented by objects of type :class:`Energy`.
Martin Reinecke's avatar
Martin Reinecke committed
226
227
228
229
230
231
These hold the prescription how to calculate the function's
:attr:`~Energy.value`, :attr:`~Energy.gradient` and
(optionally) :attr:`~Energy.curvature` at any given position.
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.
232

Martin Reinecke's avatar
Martin Reinecke committed
233
234
235
236
237
Some examples of concrete energy classes delivered with NIFTy4 are
:class:`QuadraticEnergy` (with position-independent curvature, mainly used with
conjugate gradient minimization) and :class:`~nifty4.library.WienerFilterEnergy`.
Energies are classes that typically have to be provided by the user when
tackling new IFT problems.
238

Martin Reinecke's avatar
Martin Reinecke committed
239
240
241

Iteration control
-----------------
Martin Reinecke's avatar
Martin Reinecke committed
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264

Iterative minimization of an energy reqires some means of
controlling the quality of the current solution estimate and stopping once
it is sufficiently accurate. In case of numerical problems, the iteration needs
to be terminated as well, returning a suitable error description.

In NIFTy4, this functionality is encapsulated in the abstract
: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
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
291
292
293
294
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`.

Many minimizers for nonlinear problems can be described as

- 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.


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

Martin Reinecke's avatar
Martin Reinecke committed
295
296
297
298
299
300
301
302
303
304
305
306
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
minimization of a :class:`QuadraticEnergy` by means of a
:class:`ConjugateGradient` algorithm.