Overview
A Kalman Filter predicts the next state, compares it with a measurement, and updates the estimate based on uncertainty.
ExtendedSource checked
Kalman Filter
Estimates hidden state by blending predictions with noisy measurements.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Signal Processing
- Difficulty
- Advanced
- Family
- State Estimation
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 2
- Relationships
- 1
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
state estimateprediction stepmeasurement updateuncertainty covariancesignal samplesfilter kernelstate estimationsample window
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n^3)
Average
O(n^3)
Worst
O(n^3)
Space
O(n^2)
When to Use
- Use Kalman Filter when you need to predict state forward.
- Use it for sensor fusion with inputs like previous state estimate.
- Use it when sampled data needs filtering, transformation, smoothing, or frequency analysis.
- Use it when the State Estimation tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when sample rate, window size, or boundary handling is not defined.
- Avoid it when O(n^3) worst-case behavior is too costly for the expected input size.
- Avoid it when the required output is not updated state estimate.
What It Does
- Predicts state forward
- Corrects predictions with measurements
Use Cases
- Sensor fusion
- Tracking moving objects
- Smoothing noisy measurements
Inputs
- Previous state estimate
- Measurement
- Uncertainty model
Outputs
- Updated state estimate
- Updated uncertainty
Key Formulas (2)
Prediction step
statepred = F · state + B · control
state_pred = F * state + B * controlProjects the current state estimate forward before seeing the next measurement.
Measurement update
statenext = statepred + K · (measurement − H · statepred)
state_next = state_pred + K * (measurement - H * state_pred)Corrects the prediction by the measurement residual scaled by the Kalman gain.
Pseudocode
- 1.Predict the next state from the model
- 2.Predict the next uncertainty
- 3.Compare the prediction with the measurement
- 4.Compute how much to trust the measurement
- 5.Update the state and uncertainty
Canonical Example
- Input
- samples = [1, 2, 3, 2, 1]
- Output
- transformed or filtered samples
- Explanation
- Kalman Filter: The algorithm reads local or frequency structure from the sample sequence.
Implementation Notes
- Keep the input contract explicit: Previous state estimate; Measurement; Uncertainty model.
- Use this step as the implementation spine: Predict the next state from the model.
- Then preserve the next state change: Predict the next uncertainty.
- Define boundary behavior before processing the first and last samples or pixels.
- Test with simple signals such as constants, impulses, and single-frequency waves.
Common Pitfalls
- The standard Kalman Filter assumes linear dynamics and Gaussian noise.
- Interpreting transformed values without accounting for scale, phase, or edge effects.
- Returning updated state estimate without handling empty, invalid, or boundary inputs.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow a predicted path being pulled toward noisy measurements.
Step 1 of 5: Predict the next state from the model
prediction-correctionNotes
Kalman Filter operates in O(n^3) time and O(n^2) space within the State Estimation family. Key governing relation: state_pred = F * state + B * control. Often compared with Moving Average and Gradient Descent.
Sources (1)
What each reference supports for this entry.
Kalman 1960 paper
PaperOriginal paper introducing the linear filtering and prediction method now known as the Kalman filter.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborMoving Average
Both smooth noisy observations, but Kalman filtering models state dynamics explicitly.
Related Algorithms
Tags
Signal ProcessingEstimationFiltering