Register to reply 
Inverse (LS) problem for binary data 
Share this thread: 
#1
Mar409, 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 illconditioned 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*fg 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? 


#2
Mar409, 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.



#3
Mar509, 05:15 PM

P: 523




#4
Mar509, 10:26 PM

P: 5

Inverse (LS) problem for binary data
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*fg 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 nonrobust. But thanks for your help anyway, at least I know now that I'm not missing (hopefully) anything obvious. 


#5
Mar609, 08:04 AM

P: 523

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*fg. Another approach could be to write it as an integer programming problem: minimize M*fg2*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. 


#6
Mar709, 10:23 AM

P: 5

Euclidean norm is used at the moment. I have also toyed with amount of nonzero 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*fg i.e. f_{k} = f_{k1}T(f''_{k1}), 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 adhoc, 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. 


#7
Mar709, 10:39 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

Are linear classifiers what you're looking for?



#8
Mar809, 04:58 AM

P: 523

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


#9
Mar809, 09:33 AM

P: 5

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 