Convex minimization and data recovery with linear convergence
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.
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
=
∑
i
=
1
N
x
i
x
i
T
A
n
-
1
x
i
,
A
n
+
1
=
A
n
+
1
·
tr
(
A
n
+
1
-
1
)
for each iteration n, where χ={x 1 , x 2 , . . . , x N } represents the set of data points, and ∥A n −1 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.
9. The method of claim 8 , further comprising, after iteratively computing the minimizer matrix, extracting as the subspace a top set of d eigenvectors from the computed minimizer A n+1 .
10. The method of claim 1 ,
wherein the reduced data set comprises image data having shadows, reflections or saturations removed, and
wherein processing the reduced data set to identify one or more objects comprises processing the reduced data set to identify a face captured within the image data.
11. The method of claim 1 , wherein the image processing device comprises a video surveillance device and the reduced data set comprises image data of moving objects having a background removed.
12. The method of claim 1 , wherein the multidimensional data and the reduced data set comprises a three dimensional (3D) structure.
13. The method of claim 1 , further comprising identifying the outlier data points based on the reduced data set.
14. The method of claim 1 , further comprising, prior to iteratively processing the set of data points to compute the reduced data set, inserting a plurality of artificial outlier data points to the set of data point prior to iteratively processing the set of data points to compute the reduced data set.
15. The method of claim 1 , further comprising, prior to iteratively processing the set of data points to compute the reduced data set, normalizing each of the data points to a unit sphere by dividing each of the data points to a corresponding Euclidean norm of the data point.
16. The method of claim 1 , further comprising, prior to iteratively processing the set of data points to compute the reduced data set, normalizing each of the data points to a unit sphere by dividing each of the data points to a corresponding Euclidean norm of the data point.
17. The image processing device of claim 1 ,
wherein the reduced data set comprises image data having shadows, reflections or saturations removed, and
wherein the program code processes the reduced data set to identify a face captured within the image data.
18. The image processing device of claim 1 , wherein the device comprises a video surveillance device and the reduced data set comprises image data of moving objects having a background removed.
19. An image processing device comprising:
memory to store multidimensional image data comprising a set of data points conforming to a plurality of dimensions (D) and having a set of outliers; and
a processor configured to execute program code to process the multidimensional image data to remove objects from the image data by computing a reduced data set that is representative of the multidimensional image data without the outliers,
wherein the program code iteratively processes the set of data points of the image data with the device to compute a reduced data set representative of the set of data points, 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,
wherein the program code determines, 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,
wherein the program code computes, 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
wherein the program code processes the reduced data set representative of the image data to identify one or more features within the physical environment.
20. The image processing device of claim 19 , wherein, for each iteration, the program code computes the updated estimate of the subspace by 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.
21. The image processing device of claim 20 , wherein the scaled covariance matrix comprises a scaled inverse covariance matrix.
22. The image processing device of claim 19 , wherein the program code iteratively processes the set of data points to compute the reduced data set with linear convergence with respect to the number of iterations.
23. The image processing device of claim 19 , wherein the program code re-computes 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.
24. The image processing device of claim 23 , wherein the program code, after iteratively computing the minimizer matrix, extracts as the subspace a bottom set of d eigenvectors from the computed minimizer Q k+1 .
25. The image processing device of claim 19 , wherein the program code re-computes a minimizer matrix A n+1 as:
A
n
+
1
=
∑
i
=
1
N
x
i
x
i
T
A
n
-
1
x
i
,
A
n
+
1
=
A
n
+
1
·
tr
(
A
n
+
1
-
1
)
for each iteration n, where χ={x 1 , x 2 , . . . , x N } represents the set of data points, and ∥A n −1 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.
26. The image processing device of claim 25 , wherein the program code, after iteratively computing the minimizer matrix, extracting as the subspace a top set of d eigenvectors from the computed minimizer A n+1 .