  Motivated by localization problems such as cadastral maps refinements, we
consider a generic Nonlinear Least Squares (NLS) problem of minimizing an
aggregate squared fit across all nonlinear equations (measurements) with
respect to the set of unknowns, e.g., coordinates of the unknown points'
locations. In a number of scenarios, NLS problems exhibit a nearly-separable
structure: the set of measurements can be partitioned into disjoint groups
(blocks), such that the unknowns that correspond to different blocks are only
loosely coupled. We propose an efficient parallel method, termed Parallel
Inexact Levenberg Marquardt (PILM), to solve such generic large scale NLS
problems. PILM builds upon the classical Levenberg-Marquard (LM) method, with a
main novelty in that the nearly-block separable structure is leveraged in order
to obtain a scalable parallel method. Therein, the problem-wide system of
linear equations that needs to be solved at every LM iteration is tackled
iteratively. At each (inner) iteration, the block-wise systems of linear
equations are solved in parallel, while the problem-wide system is then handled
via sparse, inexpensive inter-block communication. We establish strong
convergence guarantees of PILM that are analogous to those of the classical LM;
provide PILM implementation in a master-worker parallel compute environment;
and demonstrate its efficiency on huge scale cadastral map refinement problems.
