A vision-aided inertial navigation system comprises an image source to produce image data for poses of reference frames along a trajectory, a motion sensor configured to provide motion data of the reference frames, and a hardware-based processor configured to compute estimates for a position and orientation of the reference frames for the poses. The processor executes a square-root inverse Schmidt-Kalman Filter (SR-ISF)-based estimator to compute, for features observed from poses along the trajectory, constraints that geometrically relate the poses from which the respective feature was observed. The estimator determines, in accordance with the motion data and the computed constraints, state estimates for position and orientation of reference frames for poses along the trajectory and computes positions of the features that were each observed within the environment. Further, the estimator determines uncertainty data for the state estimates and maintains the uncertainty data as a square root factor of a Hessian matrix.