Register to reply

Inverse (LS) problem for binary data

by Zhiv
Tags: binary, data, inverse
Share this thread:
Zhiv
#1
Mar4-09, 04:27 AM
P: 5
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?
Phys.Org News Partner Science news on Phys.org
New type of solar concentrator desn't block the view
Researchers demonstrate ultra low-field nuclear magnetic resonance using Earth's magnetic field
Asian inventions dominate energy storage systems
John Creighto
#2
Mar4-09, 10:24 AM
P: 813
Try looking up neural network classifiers. I think I learned an algorithm for something like this once upon a time.
bpet
#3
Mar5-09, 05:15 PM
P: 523
Quote Quote by Zhiv View Post
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
#4
Mar5-09, 10:26 PM
P: 5
Inverse (LS) problem for binary data

Quote Quote by bpet View Post
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
#5
Mar6-09, 08:04 AM
P: 523
Quote Quote by Zhiv View Post
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 curiousity 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
#6
Mar7-09, 10:23 AM
P: 5
Quote Quote by bpet View Post
Just out of curiousity 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. fk = fk-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 intrested 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
#7
Mar7-09, 10:39 AM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,091
Are linear classifiers what you're looking for?
bpet
#8
Mar8-09, 04:58 AM
P: 523
Quote Quote by Zhiv View Post
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
#9
Mar8-09, 09:33 AM
P: 5
Quote Quote by bpet View Post
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 dunno 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 modelled 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.


Register to reply

Related Discussions
Fortran 90 (need to read in binary data files into arrays) Math & Science Software 1
Spectroscopic Binary problem.. need help fast.. Astronomy & Astrophysics 0
Eclipsing binary problem im really frustrated Astronomy & Astrophysics 3
Physics/astronomy eclipsing binary problem! help Introductory Physics Homework 1
Binary spatial data grid Set Theory, Logic, Probability, Statistics 0