Effective way to speed-up my mass-univariate problem (i.e. a large set of per-point optimization problems)

Question

I am new to numerical methods, and I have to solve a problem of medical imaging. My background is computer science. I have a naive, general question.

Problem Statement:

I have an extremly large set of points, called 'voxels' subsequently. The set is denoted by $V$. For each voxel $v\in V$, I have to solve a standard optimization problem related to the voxel $v$, i.e.,

Find the parameter $p_{min}$ s.t. $d(o^v,p_{min}) \leq d(o^v,p)$ holds for all possible parameters $p$

Above, $o^v$ is an observation at the voxel $v$, $d$ is a problem-specific (non-linear in my case) objectiver function depending on observations and model parameters. Solving this optimization problem voxel by voxel gives a correct result. However, this naive approach is not feasible as the number of voxels in V quickly becomes large.

My question is as follows:

Is there a general approach to deal with such difficulty? I am trying to find some "global method" that gives approximate solution in reasonable time. However, whenever I type "global optimization problem", I will fall into articles talking about solving global minimum (v.s. local minimum) which is different from what I need.

Any ideas? Thank you for your help.

Answer 1

Assuming you have an efficient way to find $p_{min}$ in a particular voxel, there are possible hacks to speed-up the mass-univariate problem (I would not call it global as it is indeed confusing).

If you can assume that $p_{min}$ is spatially smooth, you can harness any voxel to solve neighboring voxels. Say you use an iterating method to solve $p_{min}$, just use one solution as initialization for its neighbors.

If you cannot assume spatial smoothness in $p_{min}$, there might be hope to harness power in from parameters. If there are no more parameters, or no smoothness in any of them- the "global" problem is nothing more than a mass of separate problems.

Answer 2

If $p_{min}$ is not smooth you might do a grid search over a representative sample of $o^v$ values where the number of samples selected is less than V (but still high enough to be sufficient) and are either evenly spaced across the scale or in density space.