The integration of a feature based positioning sensor, rooted on principal component analysis, with a multi-model adaptive estimator is proposed and discussed in detail as the solution to terrain reference navigation systems for underwater vehicles. The adequacy on the use of the proposed feature based non-linear positioning sensor is studied, the error sources are enumerated, a stochastic characterization is performed, and the attainable performance is discussed, based on the results from a series of experiments for a large set of synthesized terrains. Resorting to a non-linear Lyapunov transformation, the synthesis and analysis of a multiple-model multirate adaptive estimator (MMAE) in the H-2 stochastic setting is also presented, with overall guaranteed stability and optimal performance over equilibrium trajectories. Finally, results from Monte Carlo simulations to assess the performance of the overall system are included.