Inverse (LS) problem for binary data

In summary: Euclidean norm is used at the...I'm not sure, but it sounds like the norm is used to enforce that every element of f and g is either 0 or 1.
  • #1
Zhiv
5
0
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?
 
Physics news on Phys.org
  • #2
Try looking up neural network classifiers. I think I learned an algorithm for something like this once upon a time.
 
  • #3
Zhiv said:
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?
 
  • #4
bpet said:
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.
 
  • #5
Zhiv said:
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.
 
  • #6
bpet said:
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. 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 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.
 
  • #7
  • #8
Zhiv said:
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.
 
  • #9
bpet said:
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.
 

1. What is the inverse (LS) problem for binary data?

The inverse (LS) problem for binary data is a statistical method used to estimate the parameters of a binary response model. It involves finding the values of the model's parameters that best fit the observed binary data.

2. What is the difference between the inverse (LS) problem and the forward (MLE) problem for binary data?

The inverse (LS) problem focuses on estimating the model parameters given the observed binary data, while the forward (MLE) problem focuses on estimating the probabilities of observing the data given the model parameters.

3. What types of binary response models can be used for the inverse (LS) problem?

The inverse (LS) problem can be used with various binary response models, such as logistic regression, probit regression, and logit-normal models.

4. What is the role of regularization in the inverse (LS) problem for binary data?

Regularization is used in the inverse (LS) problem to prevent overfitting and improve the stability of the parameter estimates. It involves adding a penalty term to the objective function that penalizes extreme parameter values.

5. What are some common applications of the inverse (LS) problem for binary data?

The inverse (LS) problem is commonly used in fields such as biostatistics, economics, and social sciences to analyze binary data and make predictions about binary outcomes. It has applications in areas such as medical diagnosis, market research, and social behavior analysis.

Similar threads

  • Linear and Abstract Algebra
Replies
13
Views
2K
  • Astronomy and Astrophysics
Replies
3
Views
976
  • STEM Educators and Teaching
Replies
5
Views
542
  • Introductory Physics Homework Help
Replies
8
Views
875
  • General Math
Replies
13
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
8
Views
987
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Replies
2
Views
969
  • Introductory Physics Homework Help
Replies
9
Views
636
  • Linear and Abstract Algebra
Replies
4
Views
3K
Back
Top