Inverse (LS) problem for binary data

[Zhiv]

As per topic. Is there any well established method for solving linear systems for binary data?
pardon if this is in wrong cathegory, english is not my first language and I'm not that well aware of the english terms.

i.e. the classical g = M*f problem, where g is measured data and we want to know f.
In this case, with calibration data we can determine M, but it has an ill-conditioned inverse, so the classical solution of f = M^-1*g doesn't work.

Enter the Tikhonov regularization, but it fails to be accurate enough.

Conjugate gradient method, i.e. solving min || M*f-g|| might work, if the M was positive definite, but it is not. (it's symmetrical though). Also, we demand that every element of f and g is either 0 or 1, as the measured data g is in binary form. Google scholar was of little help, so...

so in short

a) Is there any well know tools for the problem when the data is binaric

b) am I screwed?

 

[John Creighto]

Try looking up neural network classifiers. I think I learned an algorithm for something like this once upon a time.

 

[bpet]

As per topic. Is there any well established method for solving linear systems for binary data?
pardon if this is in wrong cathegory, english is not my first language and I'm not that well aware of the english terms.

i.e. the classical g = M*f problem, where g is measured data and we want to know f.
In this case, with calibration data we can determine M, but it has an ill-conditioned inverse, so the classical solution of f = M^-1*g doesn't work.

Enter the Tikhonov regularization, but it fails to be accurate enough.

Conjugate gradient method, i.e. solving min || M*f-g|| might work, if the M was positive definite, but it is not. (it's symmetrical though). Also, we demand that every element of f and g is either 0 or 1, as the measured data g is in binary form. Google scholar was of little help, so...

so in short

a) Is there any well know tools for the problem when the data is binaric

b) am I screwed?

What happens when you do row reduction?

 

[Zhiv]

What happens when you do row reduction?

Doesn't change the nature of the problem, as far as I can see. If the matrix has ill inverse (i.e. it exsits but causes numerical problems), I can't see simple algebraic manipulation taking care of it.

When it comes to the suggestion of neural networks, that could probably work, but since I'm required to solve the problem for hundreds of thousands of f for given M, it might be computationally challenging.

I have an iterative idea where we minimize ||M*f-g||

by placing constraint force on f so that it reshapes after each iteration until minimum is reached. (after all, I know the blurring process M so I know in which direction to push my guesses). And this works. The problem is that it's pretty much mathematically non-robust.

But thanks for your help anyway, at least I know now that I'm not missing (hopefully) anything obvious.

 

[bpet]

I have an iterative idea where we minimize ||M*f-g|| by placing constraint force on f so that it reshapes after each iteration until minimum is reached. (after all, I know the blurring process M so I know in which direction to push my guesses). And this works. The problem is that it's pretty much mathematically non-robust.

But thanks for your help anyway, at least I know now that I'm not missing (hopefully) anything obvious.

Just out of curiosity what norm is used? I'm assuming it's the number of nonzero elements.

Iterative solvers can be tricky to implement for binary linear systems, e.g.

M = [v1,v2], v1=[1,0,1,1,...,1]', v2=[0,1,1,1,...,1]'
g = [1,1,0,0,...,0]'

where the solution is obviously f = [1,1]' but any movement from [0,0]' to [1,0]' or [0,1]' increases ||M*f-g||.


Another approach could be to write it as an integer programming problem: minimize ||M*f-g-2*h|| for integer f and h subject to 0<=f<=1 and M*f>=2*h. If M is constant and the dimension not too big it's possible that lattice reduction techniques will help simplify the equations to make repeated solutions more efficient.

 

[Zhiv]

Just out of curiosity what norm is used? I'm assuming it's the number of nonzero elements.

Iterative solvers can be tricky to implement for binary linear systems, e.g.

M = [v1,v2], v1=[1,0,1,1,...,1]', v2=[0,1,1,1,...,1]'
g = [1,1,0,0,...,0]'

where the solution is obviously f = [1,1]' but any movement from [0,0]' to [1,0]' or [0,1]' increases ||M*f-g||.


Another approach could be to write it as an integer programming problem: minimize ||M*f-g-2*h|| for integer f and h subject to 0<=f<=1 and M*f>=2*h. If M is constant and the dimension not too big it's possible that lattice reduction techniques will help simplify the equations to make repeated solutions more efficient.

Euclidean norm is used at the moment. I have also toyed with amount of non-zero elements.
I guess they are pretty much same when the problem is binaric. I just lack mathematical rigour to check this.

Well, I'm the lucky situation that f and g are of same rank(?) same size in plain english. Also, properties of M are well know (it's basically (gaussian) model of a point spread function.) It models blurr in depth direction in 3D imaging modality.

The fact that M is PSF and that we can use the blurred data as initial guess, I now 'squeeze' the f smaller with the norm ||M*f-g||

i.e. f_k = f_k-1-T(f''_k-1), where f'' is second derivative.

T(x) = 0 if x smaller than 0, else 1

this is pretty much equal of deducing zero crossings from the vector, i.e operating


00111111000011100
would end up as
00011110000001000

This usually means that the blurred binary image is 'squeezed' to approximately right size.
(Images are 3D and we are only interested in the blur in blurr direction)

My worry (and the worry of my biophysicist advisor) is that this method is way too ad-hoc, so I was probing these forums. I guess I should have mentioned all this in the first post, but I wanted to check that I hadn't missed anything blindly obivous.

I will check out that integer trick out anyway, just in case.

 

[Hurkyl]

Are linear classifiers what you're looking for?

 

[bpet]

Also, properties of M are well know (it's basically (gaussian) model of a point spread function.) It models blurr in depth direction in 3D imaging modality.

Sorry I should have asked earlier, but by "binary" do you mean M, f, g are all binary matrices and the arithmetic uses 1+1=0, or do you mean that the elements of f are restricted to 0's and 1's?

The latter case might be easier to solve. Could you post some small (maximum 4x4) examples of M, f, g.

 

[Zhiv]

Sorry I should have asked earlier, but by "binary" do you mean M, f, g are all binary matrices and the arithmetic uses 1+1=0, or do you mean that the elements of f are restricted to 0's and 1's?

The latter case might be easier to solve. Could you post some small (maximum 4x4) examples of M, f, g.

My bad. g (and f) are restricted to 0s and 1s. M is matrix with real elements.

Well, the data is usually in class of hundreds of elements, so I don't know how much use would cutting do.


i.e. basically one 'strip' of the image looks like

(g)
0
0
1
1
1
1
0
0

when it should look like

(f)
0
0
0
1
1
0
0
0


(real data is in classes of few hundred elements, with M being n x n where n is the number of elements in g.)
This blurring is modeled my gaussian function in the M, but the inversr is ill, so something bust be done to recover the real information. At now, I use method described earlier, but I was worried that there was some easier general solution to the problem.