Publication

Efficient Kalman Smoothing for Harmonic State-Space Models

2005
Reports

Abstract

Harmonic probabilistic models are common in signal analysis. Framed as a linear-Gaussian state-space model, smoothed inference scales as $O(TH^2)$ where $H$ is twice the number of frequencies in the model and $T$ is the length of the time-series. Due to their central role in acoustic modelling, fast effective inference in this model is of some considerable interest. We present a form of `rotation-corrected' low-rank approximation for the backward pass of the Rauch-Tung-Striebel smoother. This provides an effective approximation with computation complexity $O(TSH)$ where $S$ is the rank of the approximation.

Official source

https://infoscience.epfl.ch/entities/publication/7f2f64bc-32f8-4e28-8539-5a5064f1b7d0

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2005
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/7f2f64bc-32f8-4e28-8539-5a5064f1b7d0

About this result

Related concepts (32)

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Kalman filter

For statistics and control theory, Kalman filtering, also known as linear quadratic estimation (LQE), is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, and produces estimates of unknown variables that tend to be more accurate than those based on a single measurement alone, by estimating a joint probability distribution over the variables for each timeframe. The filter is named after Rudolf E. Kálmán, who was one of the primary developers of its theory.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Related publications (14)

Efficient Kalman Smoothing for Harmonic State-Space Models

Chat with Graph Search

Acceleration of Solvers for Plasma Simulation in the Tokamak Boundary

Small-world scale-free brain networks from EEG with application to motor imagery decoding and brain fingerprinting

Challenges for AI in Multimodal STEM Assessments: a Human-AI Comparison