Model agnostic time series analysis via matrix estimation

Patent metadata

Field	Value
Publication number	US-11775608-B2
Application number	US-202217811112-A
Country	US
Kind code	B2
Filing date	Jul 7, 2022
Priority date	Jan 7, 2019
Publication date	Oct 3, 2023
Grant date	Oct 3, 2023

Abstract

A system and method model a time series from missing data by imputing missing values, denoising measured but noisy values, and forecasting future values of a single time series. A time series of potentially noisy, partially-measured values of a physical process is represented as a non-overlapping matrix. For several classes of common model functions, it can be proved that the resulting matrix has a low rank or approximately low rank, allowing a matrix estimation technique, for example singular value thresholding, to be efficiently applied. Applying such a technique produces a mean matrix that estimates latent values, of the physical process at times or intervals corresponding to measurements, with less error than previously known methods. These latent values have been denoised (if noisy) and imputed (if missing). Linear regression of the estimated latent values permits forecasting with an error that decreases as more measurements are made.

First claim

What is claimed is:

1. A system for estimating latent values of a physical process, the system comprising:
a data buffer for receiving a first time series of noisy, partial measured values of the physical process;
a representation processor coupled to the data buffer for accessing the first time series using a non-overlapping matrix representation;
an imputation and denoising circuit coupled to the representation processor for estimating a mean matrix of the non-overlapping matrix according to an exact or approximate rank of the non-overlapping matrix that is less than both its number of rows and its number of columns; and
an estimated means memory coupled to the imputation and denoising circuit for storing entries of the mean matrix as a second time series of imputed and denoised latent values of the physical process.

2. A system according to claim 1 , wherein the physical process comprises a linear recurrent function, a function with compact support, a finite sum of sublinear trend functions, or an additive combination of any of these.

3. A system according to claim 1 , wherein the representation processor comprises data indicating a number of rows and a number of columns of the non-overlapping matrix representation and an address generator for indexing the data buffer according to row and column indices.

4. A system according to claim 1 , further comprising a matrix memory for storing the non-overlapping matrix, wherein the representation processor is configured to transform the first time series in the data buffer into a Chinese page matrix in the matrix memory.

5. A system according to claim 1 , wherein the imputation and denoising circuit is configured for estimating the mean matrix by:
factoring the non-overlapping matrix as a product of a first unitary matrix, a diagonal matrix, and a second unitary matrix, wherein entries of the diagonal matrix are singular values of the first unitary matrix;
forming a reduced diagonal matrix by eliminating zero or more diagonal entries according to a threshold; and
estimating the mean matrix as the product of the first unitary matrix, the reduced diagonal matrix, and the second unitary matrix.

6. A system according to claim 1 , further comprising:
a regression processor coupled to the imputation and denoising circuit for performing a linear regression on a row of the mean matrix with respect to other rows in the mean matrix, to thereby produce a regression vector having length L; and
a forecasting processor coupled to the regression processor and estimated means memory for computing an inner product of the regression vector with the last L−1 estimated means, to thereby predict a future value of the physical process.

7. A method of estimating latent values of a physical process, the method comprising:
in a data buffer, receiving a first time series of noisy, partial measured values of the physical process;
by a representation processor, accessing the first time series using a non-overlapping matrix representation;
by an imputation and denoising circuit, estimating a mean matrix of the non-overlapping matrix according to an exact or approximate rank of the non-overlapping matrix that is less than both its number of rows and its number of columns; and
in an estimated means memory, storing entries of the mean matrix as a second time series of imputed and denoised latent values of the physical process.

8. A method according to claim 7 , wherein the physical process comprises a linear recurrent function, a function with compact support, a finite sum of sublinear trend functions, or an additive combination of any of these.

9. A method according to claim 7 , wherein accessing the first time series using a non-overlapping matrix representation includes indexing the data buffer according to row and column indices of the matrix representation.

10. A method according to claim 7 , wherein accessing the first time series using a non-overlapping matrix representation includes transforming the first time series in the data buffer into a Chinese page matrix in a matrix memory.

11. A method according to claim 7 , wherein estimating the mean matrix comprises:
factoring the non-overlapping matrix as a product of a first unitary matrix, a diagonal matrix, and a second unitary matrix, wherein entries of the diagonal matrix are singular values of the first unitary matrix;
forming a reduced diagonal matrix by eliminating zero or more diagonal entries according to a threshold; and
estimating the mean matrix as the product of the first unitary matrix, the reduced diagonal matrix, and the second unitary matrix.

12. A method according to claim 7 , further comprising:
performing a linear regression on a row of the mean matrix with respect to other rows in the mean matrix, to thereby produce a regression vector having length L; and
computing an inner product of the regression vector with the last L−1 estimated means, to thereby predict a future value of the physical process.

13. A tangible, non-transitory computer-readable storage medium, in which is stored computer program code for performing a method of estimating latent values of a physical process, the method comprising:
in a data buffer, receiving a first time series of noisy, partial measured values of the physical process;
by a representation processor, accessing the first time series using a non-overlapping matrix representation;
by an imputation and denoising circuit, estimating a mean matrix of the non-overlapping matrix according to an exact or approximate rank of the non-overlapping matrix that is less than both its number of rows and its number of columns; and
in an estimated means memory, storing entries of the mean matrix as a second time series of imputed and denoised latent values of the physical process.

14. A storage medium according to claim 13 , wherein the physical process comprises a linear recurrent function, a function with compact support, a finite sum of sublinear trend functions, or an additive combination of any of these.

15. A storage medium according to claim 13 , wherein accessing the first time series using a non-overlapping matrix representation includes indexing the data buffer according to row and column indices of the matrix representation.

16. A storage medium according to claim 13 , accessing the first time series using a non-overlapping matrix representation includes transforming the first time series in the data buffer into a Chinese page matrix in a matrix memory.

17. A storage medium according to claim 13 , wherein estimating the mean matrix comprises:
factoring the non-overlapping matrix as a product of a first unitary matrix, a diagonal matrix, and a second unitary matrix, wherein entries of the diagonal matrix are singular values of the first unitary matrix;
forming a reduced diagonal matrix by eliminating zero or more diagonal entries according to a threshold; and
estimating the mean matrix as the product of the first unitary matrix, the reduced diagonal matrix, and the second unitary matrix.

18. A storage medium according to claim 13 , further comprising computer program code for:
performing a linear regression on a row of the mean matrix with respect to other rows in the mean matrix, to thereby produce a regression vector having length L; and
computing an inner product of the regression vector with the last L−1 estimated means, to thereby predict a future value of the physical process.

Assignees

• Massachusetts Inst Technology

Inventors

• Shah Devavrat D
• Agarwal Anish
• Amjad Muhammad
• Shen Dennis

Classifications

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06F17/18 Primary

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G01D1/02

  giving mean values, e.g. root means square values (measuring root mean square values of currents or voltages G01R19/02) · CPC title

• G01D1/14

  giving a distribution function of a value, i.e. number of times the value comes within specified ranges of amplitude · CPC title