Convex minimization and data recovery with linear convergence

Patent metadata

Field	Value
Publication number	US-9251438-B2
Application number	US-201314062536-A
Country	US
Kind code	B2
Filing date	Oct 24, 2013
Priority date	Oct 24, 2012
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

A convex minimization is formulated to robustly recover a subspace from a contaminated data set, partially sampled around it, and propose a fast iterative algorithm to achieve the corresponding minimum. This disclosure establishes exact recovery by this minimizer, quantifies the effect of noise and regularization, and explains how to take advantage of a known intrinsic dimension and establish linear convergence of the iterative algorithm. The minimizer is an M-estimator. The disclosure demonstrates its significance by adapting it to formulate a convex minimization equivalent to the non-convex total least squares (which is solved by PCA). The technique is compared with many other algorithms for robust PCA on synthetic and real data sets and state-of-the-art speed and accuracy is demonstrated.

First claim

The invention claimed is:

1. A method comprising:
receiving, with an image processing device, multidimensional image data that captures a set of one or more features visible within a physical environment, wherein the image data comprising a set of data points conforming to a plurality of dimensions (D) and including outlier data points; and
removing one or more objects from the image data by iteratively processing the set of data points with the image processing device to compute a reduced data set representative of the set of data points of the image data, wherein the reduced data set conforms to a subspace having a reduced number of dimensions (d) less than the plurality of dimensions (D) of the set of data points of the image,
wherein iteratively processing the set of data points of the image data to compute the reduced data set comprises:
determining, for each iteration, a scaled version of the set of data points by re-computing a corresponding coefficient for each of the data points as a function of a proximity of the data point to a current estimate of the subspace, and
computing, for each iteration, an updated estimate of the subspace based on a minimization of a sum of least squares of the scaled version of the set of data points; and

processing, with the image processing device, the reduced data set representative of the image data to identify one or more features within the physical environment.

2. The method of claim 1 , wherein computing, for each iteration, the updated estimate comprises computing a scaled covariance matrix from the scaled version of the set of data points, wherein the scaled covariance matrix encodes the updated estimate of the subspace.

3. The method of claim 2 , wherein the scaled covariance matrix comprises a scaled inverse covariance matrix.

4. The method of claim 1 , wherein iteratively processing the set of data points to compute the reduced data set has a processing complexity with linear convergence with respect to the number of iterations.

5. The method of claim 1 , wherein the outlier data points represent noise.

6. The method of claim 1 , wherein computing, for each iteration, an updated estimate of the subspace based on a summation of weighted least absolute squares of the scaled version of the set of data points comprises computing, for each iteration, a minimizer matrix Q k+1 as:

Q

k
+
1

=

(

∑

i
=
1

N

⁢

x
i

⁢

x
i
T

max
⁡

(



Q
k

⁢

x
i



,
δ

)

)

-
1

/

tr
⁡

(

(

∑

i
=
1

N

⁢

x
i

⁢

x
i
T

max
⁡

(



Q
k

⁢

x
i



,
δ

)

)

-
1

)

for each iteration k, where χ={x 1 , x 2 , . . . , x N } represents the set of data points, and ∥Q k x i ∥ operates as the coefficient representative, for each of the data points, the proximity of the data point to the current estimate of the subspace.

7. The method of claim 6 , further comprising, after iteratively computing the minimizer matrix, extracting as the subspace a bottom set of d eigenvectors from the computed minimizer Q k+1 .

8. The method of claim 1 , wherein computing, for each iteration, an updated estimate of the subspace based on a summation of weighted least absolute squares of the scaled version of the set of data points comprises computing, for each iteration, a minimizer matrix A n+1 as:

A

n
+
1

=

∑

Assignees

• Univ Minnesota

Inventors

• Lerman Gilad
• Zhang Teng

Classifications

• G06F17/11 Primary

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06V30/194

  References adjustable by an adaptive method, e.g. learning · CPC title

• G06F18/2135

  based on approximation criteria, e.g. principal component analysis · CPC title

• G06T17/00

  Three-dimensional [3D] modelling for computer graphics · CPC title

• G06K9/66 Primary

  Physics · mapped topic