1
$\begingroup$

I have a quantity which is estimated from a number of noisy measurements. I know that the real underlying value must be some integer multiple of two quantities, e.g. $M = I_1C_1 + I_2C_2$ where $C_1$ and $C_2$ are some known (from theory) values and $I_1,I_2$ are the unknown integer multiples.

I'm casting this as a least squares minimisation problem, minimising over $I_1,I_2$ but I'm unsure of what minimisation technique is appropriate here? Is there some standard approach to this type of problem? I can get extreme values for the unknown integers by doing $ceil(M/C_i)$, so could then check every possible integer combination within that range. There are typically many such combinations though, so this would not be very efficient.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

I think this paper should be relevant to your problem:

Arash Hassibi and Stephen Boyd: Integer Parameter Estimation in Linear Models with Applications to GPS. IEEE Transactions on Signal Processing, Vol. 46, No. 11, November 1998

The authors state that the integer least-squares problem is NP-hard, but can be solved efficiently in many practical cases by the LLL algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, this is indeed a GPS processing issue, so that reference is very relevant. $\endgroup$
    – Bogdanovist
    Commented May 29, 2015 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.