The Rejected Algorithm That Helped Land Us on the Moon

In 1960, a Hungarian-born engineer named Rudolf Kalman submitted a paper describing a recursive algorithm for estimating the state of a linear dynamic system from noisy measurements. A referee at a major control theory journal rejected it, writing that the result "cannot possibly be true." Nine years later, a modified version of that exact algorithm was running on the Apollo Guidance Computer, fusing measurements from the spacecraft's inertial platform with star sightings to compute a trajectory accurate enough to land two astronauts on the Sea of Tranquility. Today it runs inside every GPS receiver, every phone, every drone, and every self-driving car on Earth.

Check out the full video on my YouTube channel Divide and Quantum.

The Problem: Estimating State From Noisy Measurements

Here is the setting. You have a system whose state evolves over time, say, the position and velocity of a spacecraft. You cannot observe the state directly. You can only take noisy measurements that depend on the state, plus your model of the dynamics is imperfect.

You want the best possible estimate of the true state at each moment. "Best" here has a precise meaning: minimum mean squared error.

You could average all past measurements. That loses information about how the state changes. You could just trust the latest measurement. That throws away everything you learned before. You could least-squares fit a trajectory through all the measurements. That works but it is expensive, grows unboundedly with time, and assumes you can store everything.

Kalman's insight was that you do not need to store the past at all. A single vector of numbers, the current state estimate and its uncertainty, is a sufficient statistic. Every new measurement updates those numbers, and the update is optimal.

The Two-Step Dance: Predict and Update

A Kalman filter alternates between two steps.

Predict: Use your model of the dynamics to project the current state estimate forward in time. Because the model is imperfect, the uncertainty grows.

Update: Take a new measurement. Combine it with the predicted state, weighting each by how confident you are in it. Because the measurement adds information, the uncertainty shrinks.

The trick is in that weighting. The filter computes a quantity called the Kalman gain, which tells you exactly how much to trust the new measurement versus your prediction. If the sensor is very noisy, the gain is small and you stick with your prediction. If the sensor is very precise, the gain is large and you mostly follow the measurement. The gain is optimal in the sense that it minimizes the variance of the resulting estimate.

The Equations

Let x be the state vector and P be its covariance (how uncertain you are). Let F be the state transition matrix (how the state evolves), H be the observation matrix (how measurements depend on state), Q be the process noise covariance, and R be the measurement noise covariance.

Predict:

x_pred = F @ x
P_pred = F @ P @ F.T + Q

Update (with measurement z):

y = z - H @ x_pred                     # innovation (measurement residual)
S = H @ P_pred @ H.T + R               # innovation covariance
K = P_pred @ H.T @ np.linalg.inv(S)    # Kalman gain
x = x_pred + K @ y
P = (I - K @ H) @ P_pred

That is it. Six lines. Run them every time a new measurement arrives, and you have an optimal state estimator.

Python Implementation

Let us track a 1D object moving with roughly constant velocity, using noisy position measurements. The state is [position, velocity].

python
import numpy as np

class KalmanFilter1D:
    def __init__(self, dt, process_var, measurement_var):
        self.dt = dt

        # State transition: position advances by velocity * dt, velocity stays
        self.F = np.array([[1, dt],
                           [0,  1]])

        # We only observe position
        self.H = np.array([[1, 0]])

        # Process noise: how much we expect the velocity to drift
        self.Q = process_var * np.array([[dt**4 / 4, dt**3 / 2],
                                          [dt**3 / 2, dt**2]])

        # Measurement noise
        self.R = np.array([[measurement_var]])

        # Initial state and covariance
        self.x = np.zeros((2, 1))
        self.P = np.eye(2) * 500  # high initial uncertainty

    def predict(self):
        self.x = self.F @ self.x
        self.P = self.F @ self.P @ self.F.T + self.Q

    def update(self, z):
        z = np.array([[z]])
        y = z - self.H @ self.x
        S = self.H @ self.P @ self.H.T + self.R
        K = self.P @ self.H.T @ np.linalg.inv(S)
        self.x = self.x + K @ y
        self.P = (np.eye(2) - K @ self.H) @ self.P

    def state(self):
        return self.x.flatten()

Running It

python
# Simulate an object moving at velocity 1.0 with noisy position readings
np.random.seed(0)
true_velocity = 1.0
true_positions = np.arange(0, 50, 1.0) * true_velocity
measurements = true_positions + np.random.normal(0, 3.0, len(true_positions))

kf = KalmanFilter1D(dt=1.0, process_var=0.01, measurement_var=9.0)
estimates = []

for z in measurements:
    kf.predict()
    kf.update(z)
    estimates.append(kf.state().copy())

estimates = np.array(estimates)
print(f"True velocity:      {true_velocity}")
print(f"Estimated velocity: {estimates[-1, 1]:.3f}")

You will see the velocity estimate converge to roughly 1.0 despite the measurements being wildly noisy. The filter is inferring velocity from the rate of change of noisy position readings, a quantity that is not directly observable, using only the current state estimate and the latest measurement.

Apollo and the Extended Kalman Filter

The original Kalman filter assumes linear dynamics and linear observations. Orbital mechanics are not linear. The Apollo navigation team, led by Stanley Schmidt at NASA Ames, extended the filter to handle nonlinear systems by linearizing the dynamics around the current estimate at each step. This is the extended Kalman filter (EKF), and its first real deployment was on the Apollo program.

The Apollo Guidance Computer had about 2 KB of RAM and ran at 2 MHz. Fitting an extended Kalman filter into that hardware, while also handling attitude control, abort guidance, and displays, was a feat of software engineering that would still be hard today. The filter fused inertial measurements (which drift) with periodic star sightings taken by the astronaut through an optical telescope. The drift in the inertial platform was corrected by the star fixes. The noise in the star fixes was smoothed by the inertial measurements. Neither sensor was accurate enough alone. Together, they were enough to hit a specific rock on the Moon.

Where You See Kalman Filters Today

GPS Receivers

A GPS receiver measures distance to several satellites (with clock noise, atmospheric delay, and multipath error), and combines them with an internal model of receiver motion. The position you see on your phone is a Kalman filter estimate, not a raw multilateration solution.

Drones and Self-Driving Cars

Every drone, quadcopter, and self-driving car fuses inertial measurements (accelerometer, gyro), wheel encoders, GPS, LiDAR, and cameras. The algorithm doing the fusing is almost always some variant of a Kalman filter, usually an EKF or an unscented Kalman filter (UKF) for highly nonlinear dynamics.

SLAM

Simultaneous localization and mapping was originally formulated as a large EKF problem, where the state vector includes both the robot's pose and the positions of all observed landmarks. Modern SLAM uses factor graphs and bundle adjustment for scalability, but the Kalman filter is still the intuition pump.

Financial Modeling

Kalman filters are used to estimate latent state variables in econometric models, track time-varying volatility, and extract signal from noisy price data.

Signal Processing

Your headphones' active noise cancellation, your phone's image stabilizer, the beamforming in your router, all use Kalman-style recursive estimators under the hood.

Limitations

Linearity

The standard Kalman filter assumes linear dynamics and Gaussian noise. Real systems are rarely linear, and noise is rarely Gaussian. The EKF and UKF extend the idea, but they lose optimality guarantees. For highly nonlinear or multimodal problems, particle filters or factor-graph methods are better.

Model Dependence

The filter's performance depends on F, H, Q, and R being reasonably accurate. If Q is too small, the filter becomes overconfident in its model and ignores real measurements. If R is too small, it chases every bit of sensor noise. Tuning these matrices is as much art as science, and poor tuning is the single most common way to break a Kalman filter in practice.

Numerical Stability

Naive implementations can have the covariance matrix P lose positive-definiteness due to floating-point error, at which point the filter diverges. Production implementations use the Joseph form of the covariance update, or better, the square-root Kalman filter, which propagates sqrt(P) instead and is numerically stable.

Why the Referee Was Wrong

The reviewer who rejected Kalman's paper thought the result was too good. You cannot, the reviewer reasoned, get an optimal estimator that uses only the current state, without storing or revisiting the past. Any real optimization problem requires looking at all the data.

The reviewer was wrong because the assumptions, linear dynamics and Gaussian noise, make the current state a sufficient statistic. All the information in the past that is relevant to estimating the present is already summarized in x and P. The algorithm does not ignore the past. It has already digested it.

That is the deep observation, and it is why the Kalman filter still runs inside essentially every device that estimates something it cannot directly observe. The referee thought it was impossible. NASA bet a program on it. The program worked.