Tikhonov Module for BioPSE

Rob MacLeod, Dana Brooks, Yesim Serinagaoglu, and Alireza Ghodrati

May 23, 2001

1 Module Overview

The purpose of this module is to apply Tikhonov regularization to an existing forward model, with flexible control of regularization type and parameters.

The overall input of the module should be a forward model matrix, geometries for the associated geometry--in the form of surfaces--and some remote boundary conditions, i.e., torso or head surface potentials.

The outputs should be an augmented forward model matrix and a set of solutions. We can describe this best with the following form of the augmented matrix:

A^TA + $\displaystyle \lambda$ R^TR

(1)

where A is the forward model, R is the regularization transform, and $\lambda$ is the regularization parameter that weights the transform. The resulting inverse solution matrix is then

A^-1 = (A^TA + $\displaystyle \lambda$ R^TR)^-1A^T

(2)

where A^T is the transpose of A.

The special feature of this module is the need for some form of feedback in order to compute multiple trial solutions as part of establishing the regularization parameter (e.g., L-curve and CRESO).

2 Design Specifics

Figure 1 shows the proposed configuration of the module, which actually consists of the following three separate modules:

[AttributeTransform: ] the purpose of this module is to generate a transform matrix that applies to attributes of a field. The types of transforms we have in mind include:
- Identity transform¹
- Spatial gradient transform
- Spatial Laplacian transform
- An arbitrary transform defined by a predefined matrix.
The usual purpose of the transform is to generate an estimate of some function of the field and we choose a matrix form because this is the most general way to represent such transforms. For example, applying the Laplacian transform to a set of potentials, L, would produce an estimate of the Laplacian at the same locations.
[RegPar Module: ] The purpose of this module is to generate a regularization parameter, $\lambda$ . The simplest form of the module would be a UI with place for the user to enter a value. More useful would be some a posteriori methods like the L-curve, CRESO, or Generalized cross validation (GCV). These latter approaches require repeated computation of test potentials for different values of $\lambda$ , hence the need for a form of feedback, described in more detail below. This complexity of function also results in the RegPar module having 5 different input ports, described below.
[Tikhonov Module: ] the main Tikhonov module has a relatively simple task; it uses the regularization parameter and the AttributeTransform module to create the augmented forward solution matrix. This module is also central to the required feedback loop

**Figure 1:** Overview of the Tikhonov module. Note the requirement for feedback from the output of the Tikhonov module and the RegPar module. This is necessary for the iterative computing of different metrics for the optimal regularization parameter.

2.1 Specific requirements to note

2.1.1 Feedback requirements

This module requires multiple computations of test solutions in order to generate a regularization parameter from a posteriori information and thus must contain a feedback loop. In Figure 1, we envision a scheme whereby the RegPar module can repeatedly call the Tikhonov module in order to generate updated augmented forward matrices. This will continue until there is a final selection of the regularization parameter, at which time the Tikhonov module will know to compute a final augmented forward matrix and pass it to the next module in the network.

There are a number of ways one can imagine implementing such a scheme; the best solution should adhere to existing feedback configurations or fit as easily as possible within the data flow paradigm. Hence, we leave it to the developers to suggest appropriate solutions.

2.1.2 Time signals as input

There will be many occasions when it will be necessary or advantageous to pass time signals as input data to the modules. This can arise in the computational of regularization parameters as well as for the case of time varying regularization.

2.1.3 Future research requirements

As part of our own proposed research in inverse solutions, there are a number of situations worth anticipating at this stage of the design. Some examples include:

Using multiple sources of input data for regularization, for instance, when there are epicardial potentials available at a small number of sites (e.g., via catheters) that we wish to use as a constraint.
Multiple space and mixed time/space regularization.

2.2 AttributeTransform module

At this point, we envision mostly surface based transform, but the module should be general enough to support any transform of attributes based on an underlying geometry. Hence we propose a separate module for this function.

2.2.1 Ports

The AttributeTransform requires only one input port:

[Input geometry: ] a Fields class port that takes the geometry of the surface--or more generally, the geometry--over which the transform will act.

and one output port:

[Output matrix: ] this matrix describes the transformation in the form of a matrix that acts on the attributes to create the transformed values.

2.2.2 UI

The UI for this module would select the type of transform to be generated. At the present time, we envision the following choices:

Identity transform, for use as an energy constraint in Tikhonov regularization.
Gradient transform, to compute an estimate of the spatial gradient of the attribute. Sub-choices would include gradient magnitude or gradient in any one direction.
Laplacian transform, to compute an estimate of the second order spatial gradient, based on either the standard four-neighbor approach for regular geometries, or one or more of the estimates described by Oostendorp and Huiskamp for irregular grid spacing.
Arbitrary transform read from a file; requires a file browser.

2.3 RegPar Module

The RegPar module is rather complex in that it must provide a means of repeated calculations of test solutions and their transformation by the forward model (and their norms). The final result will be a single best choice of regularization parameter that can be automatic or user-selected. Thus, this module must be able to implement a feedback mechanism as described above.

2.3.1 Background

Within the Tikhonov formalism there are several different approaches for finding an estimate of regularization parameter $\lambda$ . Here is a brief outline of some of them

[L-curve: ] requires constructing a curve parameterized by the regularization parameter $\lambda$ and then identifying the knee or corner of this ``L''-shaped curve. The calculations required for regularization with the identity matrix are the residual norm || Ax - b||₂ and the solution norm || x||₂. For the case of a regularization matrix R^tR substitute || R^TRx||₂.
[Generalized Cross Validation(GCV): ] Here the formula is

G = $\displaystyle {\frac{\vert\vert Ax-y\vert\vert^2}{{\rm trace}(I - A A^{I})}}$ (3)

where A^I is the inverse of the matrix A. There is alternative formula in terms of the size of A and the filter factors (which in turn depend on the singular values of A or the generalized singular values of (A, R) and on the reg param), something like m - n + $\sum_{i=1}^{\min(m,n)}$ f_i, where A is m×n and f_i is i'th filter factor.
[CRESO: ]

2.3.2 Ports

The RegPar module will require the following input ports:

[Forward model: ] this matrix will contain the forward model that describes the differential equation solution and is typically the output of a BEM (or FEM) solution.
[Regularization attribute transform: ] this matrix will contain the transform that constrains the regularized inverse solution. It is typically the output of the AttributeTransform module.
[Augmented regularized forward model: ] this matrix is the augmented form of the input, the result of a trial application of regularization and typically the output of a Tikhonov module.
[Neumann Boundary conditions: ] this field (attributes only) contains the values of potential on the outer boundary of the geometry, typically the body surface or head surface potentials.
[Trial solution: ] this field (attributes only) contains a set of trial potentials, the result of applying the augmented forward solution to the boundary conditions. This is typically another output of the Tikhonov module, and is one of the required iterative inputs from the feedback loop.

and the following output ports:

[Regularization parameter: ] the regularization parameter, both the interim value and the final best choice value
[Test results: ] the results of iteratively testing different regularizatins, e.g., the values of an L-curve, a curve of x and y values parameterized by regularization parameters value. The best format for this is not clear at this stage.

2.3.3 UI

The UI for this module must include the following elements:

[Enter reg par value: ] user may enter a regularization parameter, either the actual choice passed as output, or the starting value for an iterative scheme. In the latter case, we may wish to provide bounds on the values that the iterative scheme will scan, so select min and max values for $\lambda$ .
[Select best reg par value: ] select on the basis of a posteriori information from the iterative scheme the best value. This could be based on an L curve plot or some other minimization operation.

2.4 Tikhonov module

The Tikhonov module generates both test (and final) solutions, and also an augmented forward solution matrix.

2.4.1 Ports

The module has the following input ports:

[Forward model: ] this matrix contains the forward coefficient matrix, A.
[Regularization attribute transform: ] this matrix will contain the transform that constrains the regularized inverse solution. It is typically the output of the AttributeTransform module, R
[Regularization parameter: ] the desired regularization parameter, $\lambda$ , to combine with the regularization attribute transform.
[Neumann Boundary conditions: ] this field (attributes only) contains the values of potential on the outer boundary of the geometry, typically the body surface or head surface potentials.

and the following output ports:

[Augmented forward matrix: ] this matrix conrtains the regularized forward solution, (A^TA + $\lambda$ R)
[Solution potentials: ] this field (attributes only) is the solution based on the boundary conditions and the selected forward model, regularization transform, and regularization parameter. Note that we may want to be able to save te multiple versions of this parameter as we run through different regularization values. It should also be possible to output multiple instants in time of the soluitons.

2.4.2 UI

The UI of the Tikhonov module should be quite simple as all the real user decisions come in other modules.

3 Feedback on Design

Here is a summary of the discussion about the Tikhonov module as we proposed it.

Make a detailed list of all the approaches we can think of in the reg par module so that we can nail down just what inputs we really need; there was a lot of discussion about trying to simplify the wiring of these modules and there were a couple variations that seemd to make sense but I was not able to parse them with regard to all the various regularization approaches we might try
Oleg suggested including a preconditioned conjugate gradient solver in the Tikhonov module, which he figures will be the fastest way to compute new values for the solution. He has one he has converted from Matlab that will be done this week and would be happy to give it to us.
In this context, we should decide what other types of solutions we want to have in the Tikhonov module. As I understand it, there are advantages to SVD when we need to resolve the system many times for regularization searchs and our small systems make many options tractable.
Feedback sounds pretty straightforward. The plan would be to have separate outputs on the Tikhonov or RegPar module that would ship out the final choice for the agumented A matrix and solutions; all downstream modules would wait on those outputs.
There was a lot of discussion, fairly inconclusive in the end, about whether to think of packaging the module as Algorithms that get called from a single module or initially as modules that we eventually encapsulate as a meta-module. I think the former will end up being the most flexible and there were suggestions of collapsing the RegPar and Tikhnov into what would look like a single module that had a simpler wiring diagram than what we require with separate modules. I continue to consider the Transform module as reusable in its own right and hence worth keeping separate-others seemed to agree.
Make a pseudo code listing of the functionality we want from the entire package. Dave said that he frequently uses this approach to design his own modules because it makes it easier to see where to draw boundaries between modules.

About this document ...

Tikhonov Module for BioPSE

This document was generated using the LaTeX2HTML translator Version 99.2beta6 (1.42)

The command line arguments were:
latex2html -split 3 -no_white -link 3 -no_navigation -no_math -html_version 3.2,math -show_section_numbers tik-module

The translation was initiated by Rob MacLeod on 2001-05-23

Rob MacLeod 2001-05-23