Systems and methods for robust low-rank matrix approximation

• US 10,229,092 B2
• Filed: 08/14/2017
• Issued: 03/12/2019
• Est. Priority Date: 08/14/2017
• Status: Active Grant

• Current Assignee: City University of Hong Kong
• Original Assignee: City University of Hong Kong
• Inventors: Zeng, Wen-Jun, So, Hing Cheung, Chen, Jiayi
• Primary Examiner(s): Mai, Tan V
• Application Number:
  US15/676,600
• Publication Number:
  US 20190050372A1
• Time in Patent Office: 575 Days
• Field of Search: 708208
• CPC Class Codes: G01S 13/42 Simultaneous measurement of distance and other co-ordinates indirect measurement G01S13/46
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06F 18/20 Analysing
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: G06F 18/2136 based on sparsity criteria, e.g. with an overcomplete basis
• CPC Class Codes: G06F 2218/22 Source localisation; Inverse modelling
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06F 7/76 Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data

Abstract

Systems and methods which provide robust low-rank matrix approximation using low-rank matrix factorization in the l_p-norm space, where p<2 (e.g., 1≤p<2), providing a l_p-PCA technique are described. For example, embodiments are configured to provide robust low-rank matrix approximation using low-rank matrix factorization in the least absolute deviation (l₁-norm) space providing a l₁-PCA technique. Embodiments minimize the l_p-norm of the residual matrix in the subspace factorization of an observed data matrix, such as to minimize the l₁-norm of the residual matrix where p=1. The alternating direction method of multipliers (ADMM) is applied according to embodiments to solve the subspace decomposition of the low-rank matrix factorization with respect to the observed data matrix. Iterations of the ADMM may comprise solving a l₂-subspace decomposition and calculating the proximity operator of the l₁-norm.

Claims

1. A method for low-rank approximation of an observed data matrix, the method comprising:

obtaining, by a processor-based system, the observed data matrix;

performing, by logic of the processor-based system, factorization of the observed data matrix in l_p-norm space, wherein p<

2; and

providing, by the processor-based system from a result of the l_p-norm space factorization of the observed data matrix, a low-rank approximation comprising principal components extracted from the observed data matrix.

2. The method of claim 1, wherein obtaining the observed data matrix comprises:

deriving the observed data matrix from a signal selected from the group consisting of a data signal, a graphical signal, an audio signal, a video signal, and a multimedia signal, wherein the observed data matrix comprises a matrix of a plurality of data points representing the signal.

3. The method of claim 2, wherein providing the low-rank approximation comprises:

providing the low-rank approximation for use at least one application selected from the group consisting of a surveillance application, a machine learning application, a web search application, a bioinformatics application, a dimensionality reduction application, and a signal processing application.

4. The method of claim 1, wherein the observed data matrix comprises presence of at least one of impulsive noise, outliers, or sparse features.

5. The method of claim 1, wherein 1≤

p<

2.

6. The method of claim 5, wherein performing the factorization of the observed data matrix in the l_p-norm space comprises:

performing factorization of the observed data matrix in l₁-norm space, wherein p=1.

7. The method of claim 1, wherein performing the factorization of the observed data matrix in the l_p-norm space comprises:

applying alternating direction method of multipliers (ADMM) to solve subspace decomposition of low-rank matrix factorization with respect to the observed data matrix.

8. The method of claim 7, wherein applying the ADMM to solve subspace decomposition of low-rank matrix factorization comprises:

minimizing a residual matrix in a subspace factorization of the observed data matrix.

9. The method of claim 7, wherein applying the ADMM to solve subspace decomposition of low-rank matrix factorization comprises:

solving a l₂-subspace decomposition; and

calculating a proximity operator of the l_p-norm.

10. The method of claim 9, wherein solving the l₂-subspace decomposition comprises:

using least Frobenius norm solved by truncated singular value decomposition (SVD).

11. The method of claim 9, wherein calculating the proximity operator of the l_p,-norm comprises:

using a closed-form soft-thresholding operator for complex variables.

12. The method of claim 9, wherein solving the l₂-subspace decomposition and calculating to proximity operator of the l_p-norm are performed in each iterative step of the ADMM.

13. A system for low-rank approximation of an observed data matrix, the system comprising:

one or more data processors; and

one or more non-transitory computer-readable storage media containing program code configured to cause the one or more data processors to perform operations including;

obtain the observed data matrix;

perform factorization of the observed data matrix in l_p-norm space, wherein p<

2; and

provide, from a result of the l_p-norm space factorization of the observed data matrix, a low-rank approximation comprising principal components extracted from the observed data matrix.

14. The system of claim 13, wherein the program code configured to cause the one or more data processors to obtain the observed data matrix further causes the one or more data processors to:

derive the observed data matrix from a signal selected from the group consisting of a data signal, a graphical signal, an audio signal, a video signal, and a multimedia signal, wherein the observed data matrix comprises a matrix of a plurality of data points representing the signal.

15. The system of claim 14, wherein the program code configured to cause the one or more data processors to provide the low-rank approximation further causes the one or more data processors to:

provide the low-rank approximation for use at least one application selected from the group consisting of a surveillance application, a machine learning application, a web search application, a bioinformatics application, a dimensionality reduction application, and a signal processing application.

16. The system of claim 13, wherein the observed data matrix comprises presence of at least one of impulsive noise, outliers, or sparse features.

17. The system of claim 13, wherein the program code configured to cause the one or more data processors to perform the factorization of the observed data matrix in the l_p-norm space further causes the one or more data processors to:

perform factorization of the observed data matrix in l₁-norm space, wherein p=1.

18. The system of claim 13, wherein the program code configured to cause the one or more data processors to perform the factorization of the observed data matrix in the l_p-norm space further causes the one or more data processors to:

apply alternating direction method of multipliers (ADMM) to solve subspace decomposition of low-rank matrix factorization with respect to the observed data matrix.

19. The system of claim 18, wherein the program code configured to cause the one or more data processors to apply the ADMM to solve subspace decomposition of low-rank matrix factorization further causes the one or more data processors to:

minimize a residual matrix in a subspace factorization of the observed data matrix.

20. The system of claim 18, wherein the program code configured to cause the one or more data processors to apply the ADMM to solve subspace decomposition of low-rank matrix factorization further causes the one or more data processors to:

solve a l₂-subspace decomposition; and

calculate a proximity operator of the l_p-norm.

21. The system of claim 20, wherein the program code configured to cause the one or more data processors to solve the l₂-subspace decomposition further causes the one or more data processors to:

use least Frobenius norm solved by truncated singular value decomposition (SVD).

22. The system of claim 20, wherein the program code configured to cause the one or more data processors to calculate the proximity operator of the l_p-norm further causes the one or more data processors to:

use a closed-form soft-thresholding operator for complex variables.

23. A method for low-rank approximation of an observed data matrix, the method comprising:

obtaining, by a processor-based system, the observed data matrix;

performing, by logic of the processor-based system, factorization of the observed data matrix in l₁-norm space by applying alternating direction method of multipliers (ADMM) to solve subspace decomposition of low-rank matrix factorization with respect to the observed data matrix; and

providing, by the processor-based system from a result of the l₁-norm space factorization of the observed data matrix, a low-rank approximation comprising principal components extracted from the observed data matrix.

24. The method of claim 23, wherein applying the ADMM to solve subspace decomposition of low-rank matrix factorization comprises:

minimizing a residual matrix in a subspace factorization of the observed data matrix.

25. The method of claim 23, wherein applying the ADMM to solve subspace decomposition of low-rank matrix factorization comprises:

performing iterative steps of the ADMM, wherein each iterative step of the ADMM includes;

solving a l₂-subspace decomposition using least Frobenius norm solved by truncated singular value decomposition (SVD); and

calculating a proximity operator of the l_p-norm using a closed-form soft-thresholding operator for complex variables.