Iterated geometric harmonics for data imputation and reconstruction of missing data

• US 10,430,928 B2
• Filed: 10/22/2015
• Issued: 10/01/2019
• Est. Priority Date: 10/23/2014
• Status: Active Grant

• Current Assignee: Cal Poly Corporation
• Original Assignee: Cal Poly Corporation
• Inventors: Pearse, Erin P. J., Lindgren, Jonathan A., Eckman, Chad, Zhang, Zachariah, Sacco, David J.
• Primary Examiner(s): Misir, Dave
• Application Number:
  US14/920,556
• Publication Number:
  US 20160117605A1
• Time in Patent Office: 1,440 Days
• Field of Search: 706 12
• CPC Class Codes: G06F 17/175 of multidimensional data
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 2207/30201 Face
• CPC Class Codes: G06T 5/77 Retouching; Inpainting; Scratch removal

Abstract

Systems and methods for reconstruction of missing data using iterated geometric harmonics are described herein. A method includes receiving a dataset having missing entries, initializing missing values in the dataset with random data, and then performing the following actions for multiple iterations. The iterated actions include selecting a column to be updated, removing the selected column from the dataset, converting the dataset into a Gram matrix using a kernel function, extracting rows from the Gram matrix for which the selected column does not contain temporary values to form a reduced Gram matrix, diagonalizing the reduced Gram matrix to find eigenvalues and eigenvectors, constructing geometric harmonics using the eigenvectors to fill in missing values in the dataset, and filling in missing values to improve the dataset and create a reconstructed dataset. The result is a reconstructed dataset. The method is particularly useful in reconstructing image and video files.

Claims

1. A method for reconstructing missing data comprising:

receiving a dataset having missing entries;

initializing missing values in the dataset with random data;

performing the following actions for multiple iterations;

selecting a column to be updated and removing the selected column from the dataset,

converting the dataset into a Gram matrix using a kernel function,

extracting rows from the Gram matrix for which the selected column does not contain temporary values to form a reduced Gram matrix,

diagonalizing the reduced Gram matrix to find eigendata including eigenvalues and eigenvectors,

constructing geometric harmonics using the eigenvectors to fill in the missing values in the dataset,

filling in the missing values to improve the dataset and create a reconstructed dataset;

providing the reconstructed dataset.

2. The method of claim 1 wherein the converting is performed using K(i, j)=k(x_i, x_j) where K(i, j) is the Gram matrix and k(x_i, x_j) is the kernel function.

3. The method of claim 1 wherein the diagonalizing is achieved by computing the eigendata of K^(j)*K^(j) where K^(j) is a restricted Gram matrix.

4. The method of claim 3 wherein the computing the eigendata is achieved by evaluating

λ

_l^(j)∈

and ψ

_l^(j)∈

^|Aj|

that satisfy the following equation for l=1, . . . , |Aj|;

5. The method of claim 1 wherein the geometric harmonics are constructed according to the following equation:

6. The method of claim 1 wherein the dataset comprises multiple image files or multiple frames from a video file.

7. The method of claim 1 wherein the performing is performed for four to six iterations.

8. A computing device comprising a processor, memory and a storage medium, the storage medium having software stored thereon which when executed by the processor cause the computing device to perform actions including:

receiving a dataset having missing entries;

initializing missing values in the dataset with random data;

performing the following actions for multiple iterations;

selecting a column to be updated and removing the selected column from the dataset,

converting the dataset into a Gram matrix using a kernel function,

extracting rows from the Gram matrix for which the selected column does not contain temporary values to form a reduced Gram matrix,

diagonalizing the reduced Gram matrix to find eigendata including eigenvalues and eigenvectors,

constructing geometric harmonics using the eigenvectors to fill in the missing values in the dataset, and

filling in the missing values to improve the dataset and create a reconstructed dataset;

providing the reconstructed dataset.

9. The computing device of claim 8 wherein the converting is performed using K(i, j)=k(x_i, x_j) where K(i, j) is the Gram matrix and k(x_i, x_j) is the kernel function.

10. The computing device of claim 8 wherein the diagonalizing is achieved by computing the eigendata of K^(j)*K^(j) where K^(j) is a restricted Gram matrix.

11. The computing device of claim 10 wherein the computing the eigendata is achieved by evaluating

λ

_l^(j)∈

and ψ

_l^(j)∈

^|Aj|

that satisfy the following equation for l=1, . . . , |Aj|;

12. The computing device of claim 8 wherein the geometric harmonics are constructed according to the following equation:

13. The computing device of claim 8 wherein the dataset comprises multiple image files or multiple frames from a video file.

14. The computing device of claim 8 wherein the performing is performed for four to six iterations.