Denise: Deep Robust Principal Component Analysis for Positive Semidefinite Matrices
Authors: Calypso Herrera
Florian Krach
Anastasis Kratsios
Pierre Ruyssen
Josef Teichmann
Venue: Accepted by TMLR ()

Abstract: The robust PCA of covariance matrices plays an essential role when isolating key explanatory features.  The currently available methods for performing such a low-rank plus sparse decomposition are matrix specific, meaning, those algorithms must re-run for every new matrix.  Since these algorithms are computationally expensive, it is preferable to learn and store a function that nearly instantaneously performs this decomposition when evaluated.  Therefore, we introduce Denise, a deep learning-based algorithm for robust PCA of covariance matrices, or more generally, of symmetric positive semidefinite matrices, which learns precisely such a function.  Theoretical guarantees for Denise are provided.  These include a novel universal approximation theorem adapted to our geometric deep learning problem and convergence to an optimal solution to the learning problem.  Our experiments show that Denise matches state-of-the-art performance in terms of decomposition quality, while being approximately $2000\times$ faster than the state-of-the-art, principal component pursuit (PCP), and $200 \times$ faster than the current speed-optimized method, fast PCP. 

Published in Transactions on Machine Learning Research (05/2023)
Denise: Deep Robust Principal Component Analysis for Pos- itive Semidefinite Matrices
Calypso Herrera
allpso.herrenc@mate ethz.ch
Deportment of Mathematics
ETH Zürich
Florian Krach
florian. krach Smath, etha.ch
Department Mathematics
ETH Zürich
Anastasis Kratsios
Department Mathematics
McMaster University
Pierre Ruyssen
pierrot@google.com com
Google Brain
Google Zürich
Josef Teichmann
josef. teichneechmmnnnnno @math etha.ch
Deportment of Mathematics
ETH Zürich
Reviewed OpenReview: https:// openrevee/eerrvviee. net/ forum? D45ggggv222
Abstract
The robust PCA of covariance matrices plays essential role when isolating key explana- tory features. The currently available methods for performing such low-rank plus sparse decomposition are matrix specific, mcaning, those algorithms must re-run for every new matrix. Since these algorithms are computationally expensive, it is preferable to learn and store a function that nearly instantaneously performs this decomposition when evaluated. Therefore, we introduce Denise, a deep lcarning-baid baacing-basod algorithm for robust PCA of covari- ance matrices, or more generally, of symmetric positive semidefinite matrices, which learns precisely such function. Theoretical guarantees for Denise provided. These include novel universal approximation theorem adapted to our geometric deep learning problem and convergence to an optimal solution to the learning problem. Our experiments show that Denise matches state-offthe-art performance in terms of decomposition quality, while being approximately 2000x faster than the state-of-tho-art, principal component pursuit (PCP), and 200x faster than the current speed-optimizeed method, fast PCP.
Low-rank plus sparse decomposition, positive semidefinite matrices, deep neural networks, geometric deep learning, universal approximation
Keywords:
1 Introduction
Robust principal component analysis (RPCA) aims to find a low rank subspace that best approximates a data matrix M which has corrupted entries. is defined as the problem of decomposing a given matrix M into the sum of a low rank matrix L, whose column subspace gives the principal components, and sparse matrix S, which corresponds the outliers' matrix. The standard method via conver optimization has significantly
worse computation time than the singular value decomposition (SVD) (Wright et al. 2009 Xu et al. 2010:

---

Published in Transactions on Machine Learning Research (05/2023)
Candes et al. 2011
Chandrasckaran et al. 2010 Hsu et al.
2011
Lin et al. 2011 Recent results developing
efficient algorithms for robust. PCA contributed to notably reduce the running time (Rodriguez & Wohlberg,
2013 Netrapalli et al. 2014 Chen & Wainwright
2015 Yi et al. 2016 Cherapanamjeri et al. 2017).
However, in some cases, it is utmost importance to instantaneously produce robust low rank approxima- tions of a given matrix. In particular, finance we need instantaneously and for long time series of multiple assets, robust low rank estimates of covariance matrices. For instance, this is the case for high-frequency trading (Ait-Sahalia et al. 2010; Ait-Sahalia & Xiu 2017: 2019). Morcover, it is useful to have one proce- dure applicable to different data that provides such estimates In addition, in applications involving noise, like covariance matrices in finance, it is important to have a procodure that is insensitive to small noise perlurbations, which is not the case for classical approaches.
Our contribution lies precisely in this area by introducing a nearly instantaneous algorithm for robust PCA for symmotric positive semidefinite matrices. Specifically, we provide simple doep learning based algorithm which ensures continuity with respect to the input matrices, such that small perturbations lead to small changes in the output. Moreover, when the deep neural network is trained, only an evaluation of it is needed to decompose any new matrix. Therefore the computation time is negligible, which is an undeniable advantage in comparison with the classical algorithms. To support our claim, theoretical guarantees are provided for (i) the expressiveness of our neural network architecture and (ii) convergence to an optimal solution of the learning problem.
2
Related Work
Let ||Ml = =es |asl denote the el-morm of the matrix M. For a given > 0, the RPCA is formulated a8
minrank(L) + +|SSIk s.t M L E.5
Although it is NP-hard, approximate relaxations of this minimization problem can be solved in polynomial time. The most popular method to solve RPCA is via conver reluzation (Wright et al. 2009 Xu et al. 2010; Candes et al. 2011 Chandrasekaran et al. 20100] Hsu al.) 2011 Lin al. 2011h. consists of a nuclear- norn-regularized matrix approximation which needs time-consuming full singular value decomposition (SVD) in each iteration. Let |MM] = Σ, (M. denote the muclear norm of M, i.c. the sum of the singular values of M. Then for a given x > 0, the problem can be formulated as
min ||]||. + Al|S||e, s.t M = L L.9
(1)
The principal component pursuit (PCP) (Candes et al. 2011 is considered as the statc-of-the-art tochnique and solves (1] by an alternating directions algorithm which is a special case a more general class of augmented Lagrange multiplier (ALM) algorithms known as alternating directions methods. The inexact ALM (IALM) (Lin et al. 2011) is an computationally improved version of the ALM algorithm that reduces the number of SVDs needed.
As the previous algorithms need time-consuming SVDs in each iteration, several non convex algorithms have been proposed to solve (T) for a more efficient decomposition of high-dimensional matrices (Rodriguez & Wohlberg 2013 Netrapalli et al.) 2014 Chen & Wainwright/ 2015 Yi et al.] 2016 Cherapanamjeri et al. 2017)- In particular, the fast. principal component pursuit (FPCP) (Rodriguez Wohlberg] [2013] is an alternating minimization algorithm for solving variation of [ By incorporating the constraint into the objective, removing the costly nuclear norm term, and imposing rank constraint on L, the problem becomes
min L..
I
M -- S1β A||S||a s.l. rank(L)= rr.
The authors apply an alternating minimization to solve this equation using a partial SVD. The RPCA via via a gradient descent method.
gradient descent (RPCA-GD) (Yi et al. 2016) solves [
Our work is related to the low rank Cholesky factorization, which, among others, is used solve semidefinite
programs (Burer & Monteiro
2001 Journée et al. 2008 2010 Bandeira et al., 2016 De Sa. et. al. 2014
2

---

Published in Transactions on Machine Learning Research (05/2023)
Boumal et al. 2016 et al. 2019 Ge al. 2016). We are not only interested in the low rank approximation, but in a robust low rank approximation. In that sense, we estimate the low rank approximation of a matrix which can be corrupted by outliers. Therefore, we are using the 4 norm instead of the Frobenius norm as it is done in those works.
The closest related works to ours are Song & Shaowei 1997) and (Baes et al. 2019). which both consider neural network approaches to robust PCA. Only the latter of the two provides optimization guarantees; there the authors consider the minimization problem
- -U- UERTXA
min
(2)
where a neural network paramoterization Ug of the matrix U optimized with gradient descent to find an approximale solution for any fixed M. In particular, for every new input M the optimization has to be repeated. In contrast, we train neural network on synthetic training dataset such that the learnt param- eters can be reused for any unseen matrix M'. In particular, our learning objective is much more involved, since we want to find a function that produces good outputs Uo for all M of a certain distribution, i.e. a function that generalizes well. While our learning task is more complicated, our method has the advantage of nearly instantancous evaluation for any new matrix, once the training is finished, compared to (Bacs) et al. 2019), where a new oplimiiattio problem needs to be solved whenever the method is applied to a new matrix M.
Other related problems are matric factorization (Lee & Scung 2001 Ding al. 2010
Trigcorgis et al. 2014
Kuang et al. 2012), malrir completion (Xue el al. 2017 7
Nguyen el al. 2018 Sedhain el. al. 2015), sparse
coding Gregor & LeCun 2010 Ablin et al.] 2019 robust subspace tracking (He et al.
2011
Narayanamurthy
& Vaswani 2018) and anomaly detection (Chalapathy et al. 2017). Solomon et al. (0019) suggested a deep
robust PCA algorithm tailored to clutter suppression in ultrasound, which still depends on applying SVDs
in each layer of their convolutional recurrent neural network. Our work similar to Gregor & LLeCun (2010) in spirit, since we also train a neural network perform a complex and otherwise time-consuming task nearly instantaneously. Our method shares many properties with their encoder, inchuding continuity, differentiability, and implicit generalization over the distribution of the training set. While their encoder can only be trained in supervised manner, relying on classical (and therefore slow) methods to generate labels for the training set, it is possible to use unsupervised training for our method.
A key component of our approach is the universal approximation capability of the deep neural model im- plementing Denisc. This result is not covered by any of the available universal approximation thcorems, including those for slandard feedforward neural networks (Hornik al. 1989 Barron 1992 Kidger & Lyons, 2020 and those concerning non-euclidean geometries (Kratsios & Bilokopytov 2020 In contrast, our universal approximation result guarantees that we can generically approximate any function encoding both the geometric and algebraic structure of the low-rank plus sparse decomposition problem.
3 Denise
We present Demise an algorithm that solves the robust PCA for positive semidefinite matrices, using deep neural network. The main idea is the following: according to the Cholesky decomposition, a positive semidefinite symmetric matrix L E R=xx can be decomposed into L = UUT. If U has n rows and r columns, then the matrix L will be of rank r or less. In order to obtain the desired decomposition M = L + S, we therefore reduce the problem to finding a matrix U E Raxr such that S = M UUT is a sparse matrix, i.c. a matrix that contains a lot of zero entries. In particular, we define the matrix U = Us (M) E R as the output of a neural network. Then the natural objective of the training of the neural network is to achieve sparsity of So(M)= == M Up ( (M)T. A good and widely used approximation of this objective is to minimize the fi-norm of (MM) in 2 To achieve this, the neural network can be trained in supervised or an unsupervised way, as explained below, depending on the available training dataset. Once Denise is
The name Denise comes from Deep and Semidefinite.
3

---

Published in Transactions on Machine Learning Research (05/2023)
trained, only need to evaluate it in order to find the low rank plus sparse decomposition
M = Uo(AM)U((M)) + M Uo(M)))O(M))
of any new posilive semidefinile malrix M. Therefore, Denise considerably outperforms all existing algo- rithms in terms of speed, they need to solve optimization problem for each new matrix.
Morcover, by the construction of L = (M(M) we can guarantce the positive semidefiniteness of L. We note that in practice one may only have access to exogenously manipulated or corrupt (missing data) covariance or correlation matrices which may cause the loss of their positive semidefiniteness. For example, an empirical correlation matrix of stock returns, where the correlation between two stock returns docreasod by the risk manager, may lose its positive semidefiniteness. The issue of non positive semidefiniteness of correlation matrices in option pricing and risk management is well explained in (Rebonato & Jäckel 1998). We refer to Higham & Strabić (2016) for detailed discussion of this issue. By contrast, most algorithms do not ensure that L is kept positive semidefinite, which forces them to correct their output at the expense of their accuracy.
3.1 Supervised Learning
If a training set is available where for each matrix M an optimal decomposition into + known, then the network can be trained directly to output the correct low rank matrix, by minimizing the supervised loss
=
[|| (MM) [1..] E - (M)))
where the expectation is taken over matrices drawn from an appropriate data-generatee distribution from which the training data is sampled. We want the difference S So to be sparse as possible, therefore we use the normm, which approxinates this objective. Indeed, if this difference is sparse, then also Sa is, since the amount of non-zero entries of Sg is upper bounded by the sum of those of S and S - Sg. On the other hand, small fo-norm of S - Se would not imply any upper bound on the non-zero entries of Sg.
A synthetic dataset of positive semidefinite matrices with known decomposition can be created by simulating Cholesky factors and sparse matrices (Section 5). Moreover, classical met can be used to generate labels for any set of matrices that user would like use training set, in case the synthetic dataset doesn't 't encompass the wanted properties. However, this is not necessarily neoded, since unsupervised training be used instead.
3.2 Unsupervised Learning
In some applications only the matrix M but no optimal decomposition is known. this case, the neural network can be trained by minimizing the unsupervised loss function
(0) : E [[IM (M(M) [l))s((M)ll.l)
(4)
where, as in the supervised case, the expectation is taken over matrices drawn from an appropriate data- generating distribution from which the training data is sampled.
3.3 Combining Supervised Learning and Unsupervised Finetuning
Often the amount of available training data of a real world datasel is limited. Therefore, we consider the following training procedure. First, Denise is trained with the supervised loss function on a large synthetic datasot, where the decomposition known (Section 5.1). Then the trained network can be finctuned with the unsupervised loss function on a real world training dataset of matrices, where the optimal decomposition is unknown. This way, Denise can incorporate the peculiarities of the real world dataset.
4

---

Published in Transactions on Machine Learning Research (05/2023)
4 Theoretical Guarantees for Denise
We provide theoretical guarantees that on every compact subset of symmetric positive semidefinite matrices, the function performing the optimal low-rank plus sparse decomposition be approximated arbitrarily well by the neural network architecture of Denise. The proofs are presented in Section 0
4.1 Notation
Let Sn be the set of n-by-n symmetric matrices, Pa C S, the subset of positive semidefinite matrices and PR.n C Pr the subset of matrices with rank at most. k S n. We consider a matrix M = -Ma E Pn, e.g- of a matrix L [Li.le, E PR.n of rank
covariance matrix. The matrix M is to be decomposed at most k and sparse matrix S [Stgla, E P.. By the Cholesky decomposition (Higham 2002 Thm 10.9 b), we know that the matrix L can be represented as L UUT, where U (Wasles E R thus M UUT S.
Let Jo (2=(++)/222 T be feedforward neural network with parameters 0. As the matrix M is symmetric, the dimension of the input can be reduced from n² to n(n + 1)/2 by taking the triangular lower matrix of M. Moreover, we convert the triangular lower matrix to vector. We combine these two transformations in the operator h
h Sn (=(n+1)/2 M + (M1,1, M2.1, M2.2..... Ma.1.... Man)).
Similarly, every vector X of dimension nk can be represented as a n-by-k matrix with the operator defined as
X
g : Rnk + Bnnk
X +
X X(n-1)8+1
X ()-1))
Using h and the matrix U can be expressed as the output of the neural network (o(M) = g(Jo (h(M))) and the low rank matrix can be expressed as (M = plfo (h(M))) for
p: RR
Pk.
X ((X)g(()))))
We assume to have a set Z C Sn x Pk,. of training sample matrices L), which is equipped with a probability measure P. ie. the data-generating distribution. In the supervised case, we assume that an optimal low rank matrix for M, while in the unsupervised case, where not used, can simply be set 0. For given training sample (M, L), the supervised and unsupervised loss functions (a. Pu. Ω Z = R are defined
(., (0,,ML) = || ( (M(M))l,
(5)
and
(0. L) = |M - (fo (h(M))le,
(6)
Then, the overall loss functions defined in and can be expressed for yp E {ps:
(0) E E( (0, M, L)]
Moreover, the Monte Carlo approximations of these loss functions are given by
N Σ
N. (0)
(0, M,, L.),
(7)
N
21
where (M, L.) are i..d. samples of P. Denise can be trained using Stochastic Gradient Descent (SGD). schematic version of these supervised and unsupervised training schemes is given in the pseudo-Algorithm
A
5

---

Published in Transactions on Machine Learning Research (05/2023)
Algorithm 1 Training of Denise
Fix 0u E N E
for j 2 0 do
Sample i.idd. matrices (M,, II),..., (MN, LN) ~ IP
Compute the gradient Gj == 1 N >i= Vop(O Mi, Li)
Determine a step-size hy > 0
Set ff+1 = 82 h2
end for
4.2 Solution Operator to the Learning Problem
Our first result guarantees that there is (non-linear) solution operator to low rank plus sparse decomposition for Denise to Iearn.
2
Thus, there is optimal
Theorem 4.1. Pir a Borel probability measure P on Pn and set < < 1. Then:
(i) For every M E Pa, the set of oplimizers, argmin JM - UU |1l is non-emply and every U e UERuxE
argmin ||M - Il,, satisfies UERaxE
L: UU E argmin |M Liles. LEP
(i) There epists a mersu-beasurbble function P + Baxk satisfying for every M E Pa
f(M) E argmin |M - UU
UERwxk
(iii) There erists compact Kg S Pn such that: P(K,) 2 1- and on which f is continuous and we define the function
f K. 3 M + f(M)J(M) E Pk
Theorem 4.1
(ii)) guarantees that the map I* is continuous and can be written as the square of a continuous Trom K2 to Buxk
function
4.3 Novel Universal Approximation Theorem
We introduce structured subset of palu- functions encapsulating the relevant structural prop- erties of the solution map in (8) We fix compact X C Pn. Denise's ability to optimally solve (2) contingent on its ability to uniformly approximate any function in VC(X, == {S E C(., 3ʃ C(X, Baxk): $=
Unlike C(X,Raxn) functions in /C(X,PR.N) always output meaningful candidate solutions to 2 since they are necessarily low-rank, symmetric, and positive semidefinite matrices. Due to this non-Fuclidean structure the next result is not covered by the standard approximation theorems of Hornik et al. (1989) and Kidger & Lyons (2020). Similarly, every function in VC(X, Pk.n) encodes the algebraic property ( namely, admits point-wise Cholesky-decomppsstion which is a continuous Iga function. Thus, algebraic structure than C(X, Pk..) does. This algebraic structure puts approximation in VC(X, Pk.n) outside the scope the purely geometric approximation theorems of Kratsios & Bilokopytov (020).
VC(X,, encapsulates
Our next result concerns the universal approximation capabilities in VC(X, Pk.n) by the set of all deep neural models f P, + Pt.n with representation f = p fa o h, where fe R m(n+1) + jkkn is a deep feedforward network with activation function a. Denote the set of all such models by p.h.
The width of f E NNr, is defined as the width of fo. The activation function o defining fo is required satisfy the following condition of Kidger & Lyons 20200.

---

Published in Transactions on Machine Learning Research (05/2023)
Assumption 4.2. The activation function C(R) is non-affine and differentiable at at-least point with non-zero derivalive al that poinl.
Theorem 4.3. Let X C Pn be compact and let a E C(R) satisfy Assumption 4.2 For each e >> 0, and each f VC(X, Pk,,), there is an f E Ngg, of width at-most m(n+2k+1)+4 such that:
2
max [(M))
<E
(9)
Theorems 4.1 and 4.3 imply that No. can approximate f with arbitrarily high probability.
Corollary 4.4. Fir a Borel probability measure P on Pni < E 1, and a satisfying 4.2 some f E Ng,n of width at-most m(a+2++1)+4 such that
Then, there exists
max MEK.
(M)) ((M))-(MM)l))) <E,
(10)
where Ke was defined in Theorem
4-1
4.4 Convergence of Denise to a Solution Operator of the Supervised Learning Problem
We show that, under the assumption that Denise has identified the optimal weights minimiizing the supervised loss function, converges to an optimal solution f of Theorem 4.1 (iii). This convergence is shown both
terms of the theoretical loss (3) and using its Monte Carlo approximation the following assumptions.
We therefore operate under
Assumption 4.5. We assume to have compact subset X Pn. of matrices M such that a continuous function f X + R satisfying
f(M) E argmin I|M UU lle, UERAxK
for all M E crists. Moreover, we assume that for (MM = ((M)S(M)T the training set is given by
Z ((ML)) X-L= f
and that we consider a probubilily measure P such that P(2)=1.
By Theorem 4.1 we know that such a set X exists. For any D E N let No. C C be the set of neural networks of depth at most and let OD be the set of all admissible weights for such neural networks. Theorem 4.6. Assume Assumption 4.8 holds and let f be as in there. for every fixed depth D, the weights On of Sop NoDD are chosen such that & (0D) is minimal, then -1 f converges to 0 in mean (L'-norm) as tends to infinity.
In the following, we assume the size of the neural network is fixed and we study the convergence of the Monte Carlo approximation with respect to the number of samples N. Moreover, we show that both types of convergence can be combined. To do so, define θD {0 Op |0|2 s D}, which is a compact subspace of Op. It is straight forward to see that Op in Theorem 4.6 can be replaced by Ôp. Indeed, if the nceded neural network weights for an e-approximation have too large norm, then one can increase D until it is sufficiently big.
Theorem 4.7. Assume Assumption 4.5 holds and let f be as in there. For every E N, P-a.s.
N 4, uniformly on θp-
Let the size of the neural network D be fixed and let 0n be as in Theorem 4.6, for every fized size N of the training set, the weights 0D Ôp are chosen such that &N (0D.N) is ménimal, then
v.(0D,N)
N (OD)..
In porticular, one can define an increasing sequence (ND)DEN in N such that llfon.N f*lle, converges to in mean (I.--oorm) as D lends to infinily.

---

Published in Transactions on Machine Learning Research (05/2023)
4.5 Convergence of Denise in the Unsupervised Learning Problem
Finally, presenl the analogous results to Theorems 4.6 and 4.7 in the unsupervised setting. The primary
distinction between the supervised and unsupervised settings is that Denise is only guaranteed to converge to minimum of the unsupervised loss function (
Assumption 4.8. We assume to have a compact subset X C Pa of matrices M together with a probability measure P on the sel
3 = ((M,)) X.L=0)
(11)
that satisfies P(2) =.
In the unsupervised learning task we cannot guarantee that Denise converges to any specific target function as we did in Section 4.4 However, we can still show that its output converges to a minimum in terms of the loss function. Therefore, let us define the minimum
min SEVO(X,Pa.))
inf P s(M)le))
(12)
for which the following result holds.
Theorem 4.9. Under Assumption 4.8 if for every fined depth D, the weights @D of fop eN chosen such that p, (0p) is minimal, then D. (p) converges to the minómuu min-
Similarly, as in Section 1.4 we can also show the convergence of the Monte Carlo approximation in the unsupervised setting.
Theorem 4.10. Under Assumption 4.8 for every D E N, P-a...
iN N T. uniformly on θp.
Let the size of the neural network D be fixed and let OD be as in Theorem 4.9. If for every fixed size N of the training set, the weights 0D E ÖD are chosen such that &N (0D.N) is minimal, then
2a(OD.N)
N (w(0)).
In particular, one can define an increasing sequence (ND) DEN N such that 4.\ (fD.ND) converges to @ Pmin
D lends to infinity.
5 Numerical Results
In this sections we provide numerical results of Denise. We first train Denise with the supervised loss function synthetic training dataset and evaluate it synthetic test dataset. We also evaluate Denise synthetic test dataset which is generated with a different distribution. Finally, we test Denise on real word dataset before and after finetuning with the unsupervised loss function. The source code is avaible at httpps//githhub.ccooDppPPrfo
5.1 Supervised Training
We create a synthetic dataset in order to train Denise using the Monte Carlo approximation supervised loss function 3 In particular, we construct a collection of n-by-n symmetric positive semidefinite matrices M that can be written as
7 of the
M
So
(13)
for a known matrix Ly of rank ty S n and a known matrix Sp of given sparsity 8g- By sparsity we mean the number of zero-valued elements divided by the lotal number of elements. For example, a sparsity of 0.95 means that 95% of the elements the matrix are zeros.
To construct a symmetric low rank matrix Lu, we first sample nky independent standard normal random variables that. we arrange into n-by-ko matrix U. Then Lo is defined UUT.
8

---

Published in Transactions on Machine Learning Research (05/2023)
To construct a symmetric positive semidefinite sparse matrix So we first sample random pair (t.j) with S i < j I n from an uniform distribution. We then construct an n-by-n matrix So that has only four non- zero coefficients: the off-diagonal elements (i,j) and (j. i) are set to a number drawn uniformly randomly in 1-,, the diagonal clements (1, 8) and (j.j) are set to a number a drawn uniformly randomly in [[6] 1].
An example of a 3 matrix with (i,j) = (1, 2), b 0.2 and 0.3 is the following:
0.3
-0.2
0
S.
- 0.2
0.3
0
0
0
0
This way, the matrix Sn is positive semidefinite. The matrix So is obtained by summing different realizations 56 each corresponding to a different pair (i,j), until the desired sparsity reached.
With this method, we create a synthetic dataset consisting of 10 million matrices for the training set. Other possibilities to generate the training set exist. For example, other distributions or different levels of sparsity can be used. Diversifying the training set can lead to better performance of the trained algorithm.
To implement Denise, we used the machine learning framework Tensorflow (Abadi et al. 2015) with Keras APIs (Chollet et al. 2015). We have tested several neural network architecturos, and settled on a simple heedfforward neural network of four layers, with a total of 32 x n(n + 1)/2 parameters. Moreover, we have tested various sizes, sparsities and ranks for the samples of the training set. All results were similar, hence we only present those using size n 20, sparsity so 0.95 and rank ko = 3 in the training set. In this setting, we trained our model using 16 Google Cloud TPU-v2 hardware accelerators. Training took around 8 hours (90 epochs), at which point loss improvements were negligible.
5.1.1 Evaluation
We create a synthetic test dataset consisting of 10,000 matrices for each of the test settings, using the method presented in Section [.]] The synthetic dataset introduced in Section [5.]]s composed of randomly generated low rank plus sparse matrices of a certain rank and sparsity. Therefore, network which performs well on this random test set should also perform well on a real world datascts with the same rank and similar sparsily. The code to generate the synthetic dataset is deterministic by setting a fixed random seed.
We compare Denise against PCP (Candes et al. 2011), , IALM Lin et al. 2011 FPCP (Rodriguez & Wohlberg/ 2013) and RPCA-GD Yi et al., (2016). matlab library (Sobral et al. 2015 Bouwmans al.) 2016). Evaluation of all the algorithms was done on the same compute:]] for a fair comparison of the inference time.
All algorithms are implemented as part of the LRS
We compare the rank of the low rank matrix L and the sparsity of the sparse matrix S. We determine the approzimated rank r(L) by the number of eigenvalues of the low-rank L that are larger than & = 0.01. Similarly, we determine the approsimated sporsity s(L) by proportion of the entries of the sparse matrix $ which are smaller than e = 0.01 in absolute value.
Moreover, we compare the relative error between the computed low rank matrix and the low rank matrix Lo (i.e. the low-rank matrix from the synthetic train and test dataset), by rel.error[I, Lo) -| /ooll Similarly, we compare the relative error between the computed sparse matrix S and the sparse matrix So, by rel.error(S, So) = ||S - /oll./
To enable a fair comparison between the algorithms, we first ensure that the obtained low-rank matrices L all have the same rank. While FPCP, RPCA-GD and Denise the required rank is set, in PCP and IALM the required rank is depending on the parameter Therefore, we empirically determined À in order to reach the same rank. In particular, with À 0.56/vnn for the synthetic dataset and À = 0.64/ Vn for the real dataset, we approximately obtain rank of 3 for matrices L.
In Table [ we evaluate Denise (trained on the training set with sparsity 0.95) in 5 test settings with different sparsity sp E {0.6, 0.7, 0.8, 0.9, 0.95). Overall Denise obtains comparable results to the state-of-the- art algorithms, while significantly outperforming the other algorithms in terms of inference speed once it is
A machine with 2x Xeon CPU 25-2697 (12 Cores) 2.70GHz and 256 GIB RAM.

---

Published in Transactions on Machine Learning Research (05/2023)
trained. This is due to the fact that only one forward pass through the neural network of Denise is needed during evaluation to compute the decomposition. In contrast. to this very fast operation, the state-ofthhe-rt algorithms need to solve an iterative optimization algorithm for each new matrix.
Table 1: Comparison between Denise and state of the art algorithms where L is sampled from standard normal distribution. For different given sparsity s(S) of So, the output properties are the actual rank r (L) of the returned matrix L, the sparsity s(S) of the returned matrix S as well as the relative errors rel.error L) and rel.error(S). Additionally we report the training (only applicable for Denisc) and inference time. Results are reported as mean (sld) computed over all samples of the test sets.
r(L)
s(S)
rel.error(L)
rel.error(S)
time
((5)
Algo
train (h)
inference (ms)
PCP
2.94 (0.23)
0.17 (0.02)
0.51 (0.10)
2.45 (0.58)
73.52 (21.13)
IALM
2.92 (0.27)
0.09 (0.02)
0.64 (0.09)
3.10 (0.67)
27.88 (2.45)
0.60
FPCP
3.00 (0.00)
0.02 (0.01)
0.48 (0.08)
2.32 (0.61)
16.55 (4.11)
RPCA-GD
3.00 (0.00)
0.02 (0.01)
0.41 (0.17)
1.97 (0.93)
59.30 (17.52)
Denise
3.00 (0.00)
0.02 (0.01)
0.46 (0.16)
2.17 (0.74)
0.05 (0.00)
PCP
2.98 (0.13)
0.19 (0.02)
0.48 (0.10)
2.63 (0.67)
92.51 (25.79)
IALM
2.96 (0.19)
0.10 (0.02)
0.63 (0.09)
3.46 (0.77)
30.57 (2.79)
0.70
FPCP
3.00 (0.00)
0.03 (0.01)
0.48 (0.08)
2.63 (0.70)
10.15 (3.77)
RPCA-GD
3.00 (0.00)
0.03 (0.02)
0.39 (0.18)
2.18 (1.10)
57.45 (17.52)
Denise
3.00 (0.00)
0.02 (0.01)
0.42 (0.15)
2.26 (0.82)
0.05 (0.00)
PCP
3.00 (0.06)
0.22 (0.03)
0.45 (0.10)
2.93 (0.83)
98.25 (27.72)
IALM
2.99 (0.11)
0.11 (0.02)
0.62 (0.09)
4.06 (0.95)
29.47 (2.46)
0.80
FPCP
3.00 (0.00)
0.03 (0.02)
0.47 (0.08)
3.11 (0.86)
10.11 (4.42)
RPCA-GD
3.00 (0.00)
0.04 (0.03)
0.38 (0.19)
2.54 (1.39)
48.03 (14.37)
Denise
3.00 (0.00)
0.02 (0.01)
0.37 (0.14)
2.38 (0.95)
0.05 (0.00)
PCP
3.00 (0.06)
0.27 (0.05)
0.41 (0.11)
3.65 (1.18)
122.84 (29.65)
IALM
3.00 (0.08)
0.12 (0.02)
0.61 (0.10)
5.39 (1.33)
30.47 (2.86)
0.90
FPCP
3.00 (0.00)
0.04 (0.02)
0.47 (0.08)
4.19 (1.20)
16.43 (4.08)
RPCA-GD
3.00 (0.00)
0.09 (0.11)
0.36 (0.21)
3.26 (2.01)
60.59 (17.04)
Denise
3.00 (0.00)
0.03 (0.01)
0.30 (0.13)
2.61 (1.24)
0.05 (0.00)
PCP
3.02 (0.13)
0.30 (0.07)
0.39 (0.11)
4.84 (1.75)
124.99 (31.56)
IALM
3.00 (0.08)
0.13 (0.03)
0.60 (0.10)
7.39 (2.02)
29.67 (2.33)
0.95
FPCP
3.00 (0.00)
0.05 (0.02)
0.47 (0.08)
5.77 (1.77)
16.94 (3.58)
RPCA-GD
3.00 (0.00)
0.17 (0.24)
0.34 (0.22)
4.28 (2.96)
49.67 (13.86)
Denise
3.00 (0.00)
0.03 (0.02)
0.26 (0.13)
3.12 (1.66)
0.05 (0.00)
5.1.2
Evaluation on Differently Generated Synthetic Data
We additionally create synthetic test sets with different sparsity consisting of 10,000 matrices each, using the method presented in Section [.1 but with a different distribution. In particular, the low-rank matrices are generated using the Student's I-distribution (with parameter & = 5) instead of using the standard normal distribution. Also in this example, Denise (trained on the original training set with normal distribution and sparsily 80 = 0.95) achieves similar results, while being nearly instantaneous (Table 2
Table 2 shows that many of the benchmark robust PCA algorithms struggle to produce decompositions with competitive level of sparsity. This is likely because they are designed for general matrices and can have trouble with the added symmetry and positive definite structure present in this problem, for which Denise has a specialized inductive bias. For example, the symmetric and positive definiteness of the input matrices violate the condition of (Candes al.] [2011] Theorem 1.1) which state that the sparse part S of the input matrix M has uniformly distributed zero entries so that the PCP algorithm can recover the true decomposition of M.
10

---

Published in Transactions on Machine Learning Research (05/2023)
Table Comparison between Denise and state of the art algorithms, where is sampled from a t- distribution. For different given sparsity s(S)) of So, the output properties are the actual rank r(L) of the returned matrix L, the sparsity s(S) of the returned matrix S as well as the relative errors rel.error(L) only report the inference
and rel.error(S). Since Denise was not trained in any of the tested scttings, time. Results are reported mean (sld) computed over all samples of the test set.
r(L)
s(S)
rel.crror(L)
rel.crror(S)
time (ms)
(S5)
Algo
PCP
2.97 (0.18)
0.18 (0.02)
0.60 (0.13)
5.16 (3.27)
78.81 (22.54)
IALM
2.95 (0.22)
0.09 (0.02)
0.71 (0.10)
6.04 (3.25)
30.52 (2.23)
0.60
FPCP
3.00 (0.03)
0.02 (0.01)
0.48 (0.11)
3.89 (1.39)
11.02 (5.02)
RPCA-GD
3.00 (0.00)
0.02 (0.01)
0.51 (0.20)
4.50 (3.41)
48.81 (14.70)
Denise
3.00 (0.00)
0.01 (0.01)
0.41 (0.20)
3.67 (6.97)
0.05 (0.00)
PCP
2.99 (0.11)
0.19 (0.02)
0.58 (0.13)
5.73 (3.58)
88.22 (24.77)
IALM
2.98 (0.15)
0.10 (0.02)
0.70 (0.10)
6.81 (3.55)
29.97 (2.28)
0.70
FPCP
3.00 (0.03)
0.02 (0.01)
0.48 (0.10)
4.41 (1.53)
16.68 (4.10)
RPCA-GD
3.00 (0.00)
0.02 (0.02)
0.51 (0.20)
5.09 (3.77)
48.47 (14.52)
Denise
3.00 (0.00)
0.01 (0.01)
0.38 (0.20)
3.91 (8.88)
0.05 (0.00)
PCP
3.00 (0.06)
0.21 (0.03)
0.56 (0.14)
6.64 (4.18)
106.57 (27.99)
IALM
2.99 (0.11)
0.10 (0.02)
0.69 (0.10)
8.05 (4.13)
30.95 (2.85)
0.80
FPCP
3.00 (0.03)
0.03 (0.01)
0.48 (0.11)
5.28 (1.87)
10.02 (3.88)
RPCA-GD
3.00 (0.00)
0.03 (0.03)
0.50 (0.21)
6.00 (4.39)
57.42 (17.19)
Denise
3.00 (0.00)
0.02 (0.01)
0.35 (0.20)
4.33 (10.34)
0.05 (0.00)
PCP
3.01 (0.10)
0.24 (0.04)
0.54 (0.14)
8.81 (6.37)
99.10 (26.59)
TALM
3.00 (0.09)
0.12 (0.02)
0.69 (0.10)
10.89 (6.29)
17.78 (1.69)
0.90
FPCP
3.00 (0.03)
0.03 (0.02)
0.47 (0.11)
7.12 (2.57)
10.68 (3:27)
RPCA-GD
3.00 (0.00)
0.05 (0.07)
0.49 (0.22)
8.09 (6.69)
41.67 (13.21)
Denise
3.00 (0.00)
0.02 (0.01)
0.31 (0.21)
5.55 (19.75)
0.05 (0.00)
PCP
3.03 (0.17)
0.27 (0.06)
0.53 (0.14)
11.83 (8.03)
105.88 (26.74)
IALM
3.01 (0.12)
0.12 (0.03)
0.69 (0.10)
14.83 (7.97)
30.19 (2.18)
0.95
FPCP
3.00 (0.02)
0.03 (0.02)
0.47 (0.11)
9.79 (3.77)
10.27 (3.75)
RPCA-GD
3.00 (0.00)
0.08 (0.15)
0.48 (0.23)
10.82 (8.53)
50.14 (14.15)
Denise
3.00 (0.00)
0.02 (0.01)
0.29 (0.20)
6.85 (17.01)
0.05 (0.00)
5.2 A Note on the Computation Time of Denise
While applying the trained Denise algorithu nearly instantaneous, outperforming all competitors, its training is very time intensive. Incorporating the training time into the time measurement (normalized by the test set), iee. distributing the 8 hours of training time equally to the evaluation of the 10,000 test matrices, yields an evaluation time of 2880 ms per test sample, which is much slower than the other algorithms. Increasing the test set to the same size as the training set with 10 million samples would decrease this adjussed measurement time to less than 3 ms, outperforming the competitors again. Since this training-adjusted measurement time specific the test set size (which chosen arbitrarily), we do not show it in the tables. However, this consideration makes clear that in cases where only view matrices need to be decomposed, Denise does not offer benefit in terms of computation time over the existing methods if it needs to be trained. On the other hand, if any time improvement at inference is valuable (e.g. in high- frequency trading), Denise offers the possibility to do the computationally heavy part offline by training it for all needed combinations of matrix and output low-rank sizes beforehand such that, at inference, only its fast evaluation time matters. Moreover, if one has to decompose a large number of matrices or if one regularly ncods to decompose matrices of a known size (as would be the case in automated vidco decomposition tasks e.g. for traffic cameras), the usage of Denise can provide helpful speedup. In particular, we propose to use Denise in cases where its compilation and training can be done offline, leading compilation artifact that
11

---

Published in Transactions on Machine Learning Research (05/2023)
can be used to speed up inference significantly similar to amortized inference (Gershman & Goodman 2014
and inference compilation (Le et al. 2017 Harvey et al. 2019).
5.3 Application on S&P500 Stocks Portfolio
We consider a real world dataset of about 1'000 20-by-20 correlation matrices of daily stock returns (on closing prices), for consecutive trading days, shifted every 5 days, between 1989 and 2019. The considered stocks belong to the S&P500 and have been sorted by the GICS sectors The first. 77% of the data used training set and the remaining 23% as test set.
We perform a low-rank plus sparse decomposition of these matrices where we choose the low rank to be equal to kn = 3 as we used in the synthetic case before. This choice can be made by the user depending on their preference of the number of resulting principle components. Depending on this choice of ko the supervised training needs to be done on a corresponding synthetic training set with the same rank ku-
Denise, which was trained on the synthetic dataset with ko- 3, is once evaluated the real world test set before and once after finetuning it on the (real world) training set (Table 3). The finetuning considerable improves the performance of Denise. Upon inspection we find that Denise offers comparable performance to the leading fastest robust PCA algorithm, namely FPCP, while executing 30x faster. The synthetic test dataset composed of 10,000 matrices, while here the test dataset contains around 200 matrices. This explains why the computation time Denise is higher here, as the effort needed to launch the computations is the same no matter whether 10,000 or 200 matrices are evaluated. If repeating the test such that it has again 10,000 samples, Denise achieves the same speed Denise has the advantage of becoming (relatively) faster when applied to more samples.
the synthetic dataset (0.05 ms). In particular,
Table 3: Comparison of Denise and Denise with finetuning (FT) to the state of the art algorithms on the S&P500 dataset's test set. We report the finetuning (only applicable for Denise) and inference time. Results are reported as mean (std) computed over all samples of the test set.
Method
r(L)
s(S)
REML = IM-Alle [M
FT time (s) inference time (ms)
PCP
2.97 (0.54)
0.33 (0.06)
0.15 (0.04)
87.09 (0.02)
IALM
2.89 (0.53)
0.31 (0.06)
0.15 (0.04)
29.11 (0.00)
FPCP
2.99 (0.13)
0.24 (0.08)
0.11 (0.03)
17.91 (0.02)
RPCA-GD
3.00 (0.07)
0.19 (0.08)
0.22 (0.05)
61.23 (0.03)
Denise
3.00 (0.00)
0.08 (0.02)
0.18 (0.03)
0.66 (0.00)
Denise (FT)
3.00 (0.00)
0.15 (0.04)
0.15 (0.04)
45
0.62 (0.00)
5.4 Discussion of the Computational Challenges for Denise
In general, the two main computational challenges in deep learning high-dimensionality and low-regularity of the target map. While they often appear together, in our experimental setup the dimension of the problem is relatively low for deep lcarning standards not posing an obstruction. However, the Icarnability of the highly irregular function performing the robust PCA decomposition truly is computational challenge shown to be surmounted by Denise in our experiments.
This can be seen, for example, by examining the optimal approximate rates for ReLU neural networks, when approximating continuous functions and smooth functions between Euclidean spaces; see Shen et al. (2022) and Tuu et al. 2021), respectively. Consider the case of 400 dimensional inputs, as in the 20 20 matrices in Section 5.3 The former of these optimal approximation theorems guarantees that the uniform approximation
3 "Accrrding the global industry classficaaton standard: energy, , materials, industrials, estate, consumer discretionary, consumer staples, health care, financials, information technology, communication services, utilities.
12

---

Published in Transactions on Machine Learning Research (05/2023)
M
L (PCP)
S (PCP)
M
L (IALM)
S (IALM)
(FPCP)
(FPCP)
M
L (RPCA-GD)
S (RPCA-GD)
M
L (Denise (FT))
S (Denise (FT))
Figure 1: Decomposition into low-rank plus sparse matrix of the correlation matrix of a portfolio of 20 stocks among the P500 stocks. The forced rank is set to k = 3. We have || - L||=/||M|]] at 0.15 for PCP, 0.15 for TALM, at 0.11 for FPCP, at 0.22 for RPCA-GD and at 0.15 for Denise. The reconstruction metric || - L - [|]///||//>>>>> is for all algorithms. The computation times in milliseconds are: 103.24 for PCP, 28 66 for IALM, 15.20 for FPCP, 58.17 for RPCA-GD and 0.62 for Denise.
13

---

Published in Transactions on Machine Learning Research (05/2023)
of an a-Hölder continuous target function from compact subset X C Pau to Pk,20. any given precision >> 0, requires a network depending on roughly O ((200777) trainable parameters. The latter one implies that if this target function is sufficiently smooth the number of parameters determining this network can be polynomial in The same must be true for Denise, which can be seen by relying on the quantitative non-Euclidean universal approximation theorem of (Kratsios & Papon 2022, Theorem 9) instead of the qualitative version in Kratsios Bilokopytov (2020) that we used in the proof of Theorem 4.3
Theorem shows that the function performing the robust PCA decomposition, namely f*, is highly irregular and thus difficult to learn. This is because it is not smooth on P20, but only continuous suitable compact set Kg thereof. Therefore, our experiments illustrate that Denise can actually learn this highly irregular map, which is provably challenging for any deep learning model. Moreover, it does so while offering competitive performance to any of the stee "matrix- wise algorithms.
6 Proofs
6.1 Proof of Low Rank Recovery via Universal Approximation
Let (P,,, dist B) = | - Blle,) be the metric space of n x n symmetric positive semidefinite matrices with real coefficient. Let C(X, Pv.n) be the set of continuous functions from X to PE.,, given any (non-empty) subset X C Pn. Analogously
al., 1993). the C(X, Pk.n) is made topological space, by equipping with the topology of uniform convergence on compacts, also called compact-convergence, which is generated by the sub-basic open sets of the form
(Leshno
Bx(f,e) = { (EC((,PPa)) [1f(z) s(x)lle, <ej.
=ek
where 0, K C X compact and f E C(X, Pk,)) In this topology, sequence {fibien in C(X, Pk.n) converges to a function f E C(X, Pk,.) if for every non-empty compact subset K C X and every e > 0 there exists some N E N for which
sup =eK
- f(x)ll,, < for all jz N.
This topological space is metrizable. inclusion C(X, Pk.n) (sce (Munkres 2000. Chapter 18)).
The topology on (C(X,Pe,)) is the subspace topology induced by
Proof of Theorem 4.1 For every M E Pn. the map from gaxk to IR defined by U + || - UU lle is continuous, bounded-below by 0, and for each the set
{U E Rank IM - UU S
(14)
is compact in Roxk Thus, the map U + || - UUT [|, is coercive in the sense of (Focardi 2012 2.1). Hence, by (Focardi 2012 Theorem 2.2), the set
Definition
argmin |MM - UU UERaxk
is non-empty. Furthermore, by the Cholesky decomposition HHghamm 2002 Pk. there exists some U E Rank such that L = UUT. Since, conversely, for every U E Bank the matrix UUTE E Pkn we obtain (i).
Theorem 10.9), for every L E
Any given M E P, is positive semidefinite and therefore e, Me1 2 0, where e E R" has entry 1 its first component and all other entries equal to O. Therefore, MI,1 = e Mej 2 and in particular, / /M,, R. Therefore, the matrix U defined by Ü. 4 where 4=j=1 = 1 if 1 = i == and 0 otherwise, is in n C Ra Moreover, Ò satisfies |0OT lle, ||M Thus, by the triangle inequality, the set
DM : (U Rxn |I UU 11, s 211Ma
14

---

Published in Transactions on Machine Learning Research (05/2023)
is non-empty. Furthermore, by 14 it is compact. In summary,
0 + argmin |M UU"Ila lle, argmin M -UT
(15)
UEDx
UERaxa
Hence f(M,, described by condition (ii), equivalently characterized by
S(M) E argmin ||M 1e, for all M E Pn
(16)
DEDM
The advantage of 16) over condition (ii) is that the DM, is compact, whereas Baxk is non-compact. For any set Z denote its power-set by 2 Define the function o by
Φ: Pm + 2
M-
Next, we show that Φ is a weakly measurable correspondence in the sense of (Aliprantis & Border 1999 Definition 18.1). This amounts to showing that for every open subset S guxk the set := [M E P. (MM) nu + 0} is Borel subset of Pa.
To this end, define the function
G: x Raxk R
(M.U) + M|,, - M|M-||MP UUTTee
and let p be the canonical projection P. x Bank Pn laking (M,U) to M. Observe that, for any non-emply
open U C Baxk we have that
[ [c) (P, x 2)]
Since G is continuons and [0, 2o) is closed in IR then G [[0, oc)] is closed. Since both Ra* and Pa are metric sub-spaces of RR= then they locally-compact, Hausdorff spaces, with second-countable topology. Thus Cohn 2013 Proposition 7.1.5) implies that the open set Pa x U UseN Kj where {KiljeN is collection of compact subsets of Pa x Raxk
Since P, and Faxk are a-compact, i.c. the countable union of compact subsets, Ps Rank is also o-compact by Willlrdd 1970 Page 126). Let (Ci) be compact cover of Pa x Rank Since Pa Bank is Hausdorff (as both Pr and Ign are), each C2 n [[O, oo)] is compact and therefore {K₃ n [C, n [[0, oo) J is a countable cover of [[), n x Uf) by compact sets. Finally, since p is continuous, and continuous functions map compacts to compacts,
ú =p G 20) x0]
U [C n K2 IJEN
U Up(GnG-1(0.0 Ky]; ijEN
hence ú is an F, subset of Pn. and therefore Borel. In particular, for each open subset U S gaxk the corresponding set ú is Borel. Therefore, is weakly-measurable correspondence taking non-empty and compact values in 2
Define, the continuous function
F: P x Baxk [0, oc),
(M,U) - JI ll.
The conditions of the (Aliprantis Border 1999 Measurable Maximum Theorem; Theorem 18.19) are met and therefore there exists Borel measurable function f from P, to Bank satisfying
f(M) E argmin||M - UU = argmin I|M UUT || Ueanik
UEDa
15

---

Published in Transactions on Machine Learning Research (05/2023)
for every M& Pn. This proves (ii).
Fix a Borel probability measure P on P.. Since Pn is separable and metrizable then by (Klenke 2013 Theorem 13.6) F' must be Radon measure. Moreover, since I and P. are locally-compact and second- countable topological spaces, then, the conditions for Lusin's theorem (see (Klenke) 2013 Exercise 13. (8.1.3) for example) are met. Therefore, for every < I there exists a compact subset K S Pn satisfying IP (K+) 2 1- and for which is continuous on Kg. That is, flk. ((K,,RuXh, Moreover, since p is continuous, then
1010) po Mk. VC((,, Pk.n).
This gives (iii).
Proof of Theorem 4.5 Let N2 22--n(x+1). denote the collection of deep feed-forward networks in
Noraarrow
No 1) of width at-most m(x+2k+1)44 Note that the approximation condition
19 holding for all
2
>> O, and all f E VC(X, Pk,)) is equivalent to the topological condition {po vect E A no.narrow
1)(x+1),8n
is dense in VC((XPP..) for the uniform convergence on compacts topology. We establish the later.
Fix a a E C(R) satisfying condition C(Im(n+1)/2 (R in the topology of uniform convergence on compacts.
4.2 By (Kidger & Lyons 2020),
N 2nx+(())) is dense
Narnarrow
Let o= o 12 o (1, where 4 : X Pa. 12 PA + Sn are the inclusion maps. Since h, 12, and 4 are all continuous and injective, is 6. Observe that, 9 continuous bijection with continuous inverse. Thus, narrow Ny-naroww
Kratsios & Bilokopytov
2020 Proposition 3.7) implies that 2 1n(a411)). is dense in C(o(X), ()) if and No-narrow
only if No..martow A foofod: 3.0
2-1n((+))) is dense in C(X, ((x)R)
Let R. : Bank B U + OUT E Pk Consider the map R. sending any f E C(X, to the map Ro E PR.)). By (Munkres) 2018 Theorem 46.8) the lopology of uniform convergence on compacc compacts C(X,Rux Rn and C(X, Pk.n) are equal to their respective compact-open topologies (see (Munkres 2000 page 285) for the definition) and by (Munkres 2000) Theorem 46.11) function composition is continuous for the compact-open topology; whence, R. continuous. Moreover, by definition, its image is VC(X, Pk.n) and therefore, R. is a continuous surjection as a map from R"*k) to Ph.m). Since continuous maps send dense subsets of their domain to dense subsets of their image, R. | Ng 2224((x1))kmm C Noo is dense in VC(X,Pk,a)) As density is transitive, No Na is dense in VC(X, Pk.))- J Mp
(Rogo f
Proof of Corollary 4.4 By Theorem 4.1 and { the map f* P. PR,n is continuous on K Since Ke
is compact, Theorem 4.3 implies that there exists some f E No of width at-most m(n+2k-1)+4 satisfying:
2
max (M) (M) <.
6.2 Proof of Convergence of Supervised Denise to a Solution Operator of the Learning Problem
Proof of Theorem 4.6 By our assumption on X it follows from Corollary 4.4 that for any e >> 0 tteee exists some and weights 0p such that fap E &No and p.b - Soo (oo <e
max MEX
Since expectations are taken with respect to P which is supported on Z and since the weights Op are chosen to optimize the loss function, we have p(0p) < (00)) and hence
((0p) = E(M,L)~7 [1 (M) - 10000-((M0 (AMIle,
< B(M.L)>
[1 (M)
(MOlle))
S.
16

---

Published in Transactions on Machine Learning Research (05/2023)
Hence, we conclude that for any fixed O, there exists D1 O such that for all D> In other words, we have that
> D1, get
((, [M10 - f (M()) s..
E |1.00 - D-ixc 0,
which concludes the proof.
6.3
Proof of Convergence of the Monte Carlo Approximation
The following Monte Carlo convergence analysis is based on (Lapeyre & Lelong 2019 Section 4.3). In comparison them, we do not need the additional assumptions that were essential in (Lapeyre Lelong, Section 4.3), Le, that all minimizing neural network weights generate the same neural network output.
2019
6.3.1
Convergence of Optimization Problems
The following lemma is a consequence of (Ledoux & Talagrand 1991 Corollary 7.10) and (Rubinstein Shapiro 1993 Sec. 2.6, Lemma A1 & Theorem A1 and discussion thercafter).
Lemma 6.1. Let (E:)z1 be a sequence of i.i.d random variables with values S and h Rd x + R be a measurable function. Assume that a.s., the function E(suppo),c (1(0, < +oc. Then, a.s. fN : Rd + R,, + t E h(0, Es) converges locally uniformly to the conlinuous function f Rdd + R, B(h((0,))),
F h(0,E1) is continuous and for all C >
1
lim sup
M(0 - B(h(0, = N
Σ 1=1
0.8.
No000 18|.50
Moreover, lel the random variables Un = infzek In(æ), consider minimizing sequence (#n) given by fa(In) = inf K fa(x) and let v* = inffee f(x) and K = {or E K : f(x) = =v}. Then un + v² and d(r,,K" - a.s.
6.3.2 Strong Law of Large Numbers
R Let (M,, Ly)521 be ii.d. random variables taking values in Z = X xX) Baxn x Raxe =: S. We first remark that S a separable Banach space. Moreover, since fX) is compact as the continuous image of the compact set X, it is bounded. Hence, there exists bounded continuous function u: Raxx + Raxx such that (x))(x) is the identity. Then we define
h(0, (M,, - fe(,
where fo E NoD is neural network of depth D with the weights 0.
Lemma 6.2. The following properties satisfied.
(P1) There exists such that for all Z -M, and 0 θd we have (o S K.
(P2) Almost-surely the random function f E ê + fo is uniformly continuous.
Proof. By definition of the neural networks with sigmoid activation functions (in particular having bounded outputs), all neural network outputs are bounded in terms of the norm of the network weights, which is assumed to be bounded, not depending on the norm of the input.
Since the activation functions are continuous, also the neural networks are continuous with respect to their weights 8, which implics that also 0 θअ fo is continuous for any fixed input. Since θx is compact, this automatically yields uniform continuity almost-surely and therefore finishes the proof of (Pz).
17

---

Published in Transactions on Machine Learning Research (05/2023)
Proof of Theorem 4- We apply Lemma 6.1 to the sequence of i.i.d random function h(0, (M,,, L,)). With (Pi) of Lemma 6.2 and since is bounded we know that also
[h(0, L,)1 = [I((,))le, + llfo(M)
is bounded for 8 θp. Hence, there exists some B > such that
B(M
sup |h(0,, (M,, B <8<000 DEôn
(17)
By (P2) of Lemma 6.2 the function 0 + h(0) is continuous. Therefore, can apply Lemma 6.1 yielding that almost-surely for N + oo the function
0
h(0 (Mj, L,)) ()) ()
converges uniformly on ÔM to
0 - Ep (M1, L1)) = (0),
where we used that is the identity on (X)
Let @winn C Op be the subset of weights that minimize D.. We deduce from Lemma 6.1 that d(0p,N O 4 O a.s. when N + Then there exists sequence (θD,N) NeN in Omin such that 10D.N 0D la - 0 a.s. for N xo. The uniform contimuity of the random functions f + fo on θD implies that IfeD.N foo,N No.. 12 a.s.
when N + xc. By continuity of e and the f--orm this yields [1(0p,,, (M1, L.)) 1(OD,N (Mi, L.)) - a.s. as N co. With [7 we can apply dominated convergence which yields
Jim Ep [1h(0D.N, (M1, L1)) h(OD.N, (M1, LiDII (M1,L)))
0.
N
Since for every integrable random variable Z we have 0 < [E|Z] S E[|Z]] and since 0D O we can deduce
lim (,D,NN lim Ex [1(OD,N (M1, I4)] N
N
lim E₂ | (M1, N
= (Op).
(18)
We define No == O and for every D E
ND == min (N ENENNNN ND-1, (bb,,) 2.(0D) s #1
which is possibly due to 18 Then Theorem 4.6 implies that
Ep [100.N, (M) (M) 4. s + +, D-+00 0,
which concludes the proof.
6.4 Proof of Convergence of Denise in Unsupervised Learning Task
Proof of Theorem
4.9
Fix c >>>0 0. Let fe E VC(X, Pk...) be such that B fe(M)lle, < Pmin + c.
From Theorem 4.3 we know that there exists some depth D and weights 0D such that the resulting neural
network fh E No g. satisfies maxMeR Ilfe (M) for (M)lle Since Op E Op is chosen to minimise &...
get by triangle inequality
(aD) (,(0 -EMM,yy=lllM. Säg (M)llea)
E <B.ML)~FIIMM ([allMM-(MMM) fc(M)) B.M.. -
Pmin + 2c.
18

---

Published in Transactions on Machine Learning Research (05/2023)
Since (u(0 2 Pmin by definition, we have (P,(9)) Pminl S (@a(0D) -minn S 2c. Using that du(OD) is decrcasing in D, we can conclude that (+p)(D)) - 4 miul D- 0.
Proof of Theorem 4.10 The first two claims follow analogously as in the proof of Theorem 4.7 soquence ND similarly in the proof of Theorem 4.7 combining these first two results and Theorem 4.9 via triangle inequality proves that @ (0D,N>) converges to 4 min.
Choosing the
7 Discussion
We provide a simple deep learning based algorithm to decompose positive semidefinite matrices into low rank plus sparse matrices. After the deep neural network was trained, only an evaluation of it is needed to decompose any new unseen matrix. Therefore, the computation time is negligible, which is an undeniable advantage in comparison with the classical algorithms. To support our claim, we provided theoretical guarantees for the recovery of the optimal decomposition. To the best of our knowledge, this is the first time that neural networks used to learn the low rank plus sparse decomposition for any unseen matrix. The obtained results are very promising. We believe that this subject merits to be further investigation for all online applications where the decomposition must be instantancous and stable with respect to the inputs.
In future work, Denise's s algorithm can be extended to no longer require M to be positive semidefinite such that M can be any n X n matrix. This can be achieved by replacing the feature map h with standard vectorization operation. Furthermore, Denise's deep learning architect can be modified to encode different structures in by modifying its output layer. E.g. full-rank matrices can be produced using the output layer /radoout-map described in (Kratsios & Papon 2022 Section 3.4.2) and examples of other structures which can be encoded in L by modilying Denise's 's output layers can be borrowed from Meyer et al. 1201
Acknowledgement
We thank Hartmut Maennel, Maximilian Nitzschner, Thorsten Schmidt and Martin Stefanik for valuable re- marks and helpful discussions. Moreover, the authors would like to acknowledge support for this project from the Swiss National Science Foundation (SNF grant 179114) and partially funded by the NSERC Discovery grant (RGPIN-2023-04442)
References
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Gcoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozelowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Leven- berg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Tlya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiao- qiang Zheng. Tensorflow: Large-scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org org.
Pierre Ablin, Thomas Moreau, Mathurin Massias, and Alexandre Gramfort. Learning step sizes for unfolded sparse coding. XrXiu preprint arXiv: 1xxX:i1100.1111 1att..90011177 11071, 2019.
Yacine Ait-Sahalia and Dacheng Xiu. Using principal component analysis to estimate a high dimensional factor model with high-frequency data. Journal of Econometrics, 201 - 399, 2017. ISSN 0304-4076.
Yacine Aît-Sahalia and Dacheng Xiu. Principal component analysis of high-frequency data. Journal of the American Statistical Association, 114(525):287 303, 2019.
Yacine Ait-Sahalia, Jianqing Fan, and Dacheng Xiu. figh-frequency covariance estimates with noisy and asynchronous financial data. Journal of the American Statistical Association, 105(492):1504-1117 2010.
19

---

Published in Transactions on Machine Learning Research (05/2023)
Charalambos D. Aliprantis and Kim C. Border. Infinite-dimensionall analysis. Springer- Verlag, Berlin, second edition, 1999. ISBN 3-540-65854-8. A hitchhiker's guide.
Michel Baes, Calypso Herrera, Ariel Neufeld, and Pierre Ruyssen.
Low-rank plus sparse decomposition of covariance matrices using neural network parametrization. arXiv preprint, pp. arXiv:1908.00440 2019.
Afonso S. Bandeira, Nicolas Boumal, and Vladislav Voroninski. On the low-rank approach for semidefinite programs arising in synchronization and community detection. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, 2016.
Andrew R Barron. Neural net approximation. In Proc. 7th Yale workshop on adaptive and learning systems. volume 1, pp. 69 72, 1992.
Nicolas Boumal, Vladislav Voroninski, and Afonso S. Bandeira. The non-convex works on smooth semidefinite programs. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 2765-2773, 2016.
approach
Thierry Bouwmans, Necdet Serhat Aybat, and El-hadi Zahzah. Handbook of Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing. 2016. ISBN 1498724620,
9781498724623.
Samuel Burer and Renato D.C. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming (series B, 95:2003, 2001.
Emmanuel J. Candes, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? J. ACM, 5833):11:1111:333 June 2011. ISSN 0004-5411.
Raghavendra Chalapathy, Aditya Krishna Menon, and Sanjay Chawla. Robust, deep and inductive anomaly detection. In Joint European Conference on Machine Learning and Knowledge Discovery in Datahases. pp. 36-51. Springer, 2017.
V. Chandrasekaran, P. A. Parrilo, and A. S. Willsky, Latent variable graphical model selection via convex optimization. In 2010 48th Annuol Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1610-1613 2010.
Yudong Chen and Martin Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint Nkkt:1559.030022 2015.
Yeshwanth Cherapanamjeri, Kartik Gupta, and Prateek Jain. Nearly optimal robust matrix completion. Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Muchine Learning Research, pp. 797 805, 2017.
François Chollet et al. Keras, 2015.
Donald L. Cohn. Measure theory. Birkhäuser Advanced Texts: Basler Lehrbüccher. [Birkhäuser Advancod Texts: Basel Textbooks). Barkhäuser/Sprinee,, New York, second edition, 2013. ISBN 978-1-4614-695551; 978-1-4614-6956-8.
Christopher De Sa, Kunle Olukotun, and Christopher Ré. Global convergence of stochastic gradient descent for some non-convex matrix problems. arXio preprint 1rX.m:1411.1194, 2014.
C. H. Q. Ding, T. Li, and M. 1. Jordan. Convex and nomeatinnee matrix factorizations. IEEE Trans- actions on Pattern Analysis and Machine Intelligence 32(1):45-55, 2010.
Matteo Focardi. 7-convergence: tool to investigate physical phenomena across scales. Mathematical Methods in the Applied Sciences, 35(14):1613 1658, 2012.
Rong Go, Jason D. Lec, and Tengyu Ma. Matrix completion has no spurious local minimum. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 2981-2989, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
20

---

Published in Transactions on Machine Learning Research (05/2023)
Samuel Gershman and Noah Goodman. Amortized inference in probabilistic reasoning. In Proceedings of the annual meeling of the cognilive science society, volume 36, 2014.
Karol Gregor and Yann LeCun. Learning fast approximations sparse coding. In Proceedings of the 27th international conference on international conference on machine learning, pp- 390-406, 2010.
William Harvey, Andreas Munk, Atalm Günes Baydin, Alexander Bergholm, and Frank Wood. Attention for inference compilation. aixiv preprint arXiv: 119.11161,111,,,, 2019.
Jun He, Laura Balzano, and John Lui. Online robust subspace tracking from partial information. arXiv preprinl ar X 100.33877, 2011.
Nicholas Higham. Accuracy and stability of numerical algorithms, volume 80. Siam, 2002.
Nicholas J. Higham and Nataša Strabić. Bounds for the distance to the nearest correlation matrix. SIAM Journal on Matrix Analysis and Applications, 37(3):1088 111011008-11,,, 2016.
Kurt Hornik, Maxwell Stincheombe, and Halbert White. Multilayer feedforward networks are universal approximators. Newral networks, 2(5):359 366, 1989.
D. Hsu, S. M. Kakade, and T. Zhang. Robust matrix docomposition with sparse corruptions. IEEE Trans- actions on Information Theory, 722117472, 2011.
Michel Journée, Francis Bach, P-A Absil, and Rodolphe Sepulchre. Low-rank optimization for semidefinite convex problems. Xrv preprint arXiv:0807.4423 2008.
Michel Journée, Francis Bach, Pierre-Antoine Absil, and Rodolphe Sepulchre. Low-rank optimization ion on the cone of positive semidefinite matrices. SIAM Journal on Optimization, 20(5):2327-233) 2351,, 2010.
Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2306 2327. PMLR, 09 12 Jul 2020.
Achim Klenke. Probability theory: a comprehensive course. Springer Science Business Media, 2013.
Anastasis Kratsios and levgen Bilokopylov. Non-euclidean universal approximation. Advances in Newral Information Processing Systems, 2020.
Anastasis Kratsios and Léonie Papon. Universal approximation theorems for differentiable geometric deep
learning. Journal of Machine Learning Research, 23(196):1 1-:0)):::3333111 2022.
Da. Kuang, Chris Ding, and Haesun Park. Symmetric Nonnegative Matrix Factorization for Graph Clustering. pp. 106 117. 2012.
Bernard Lapeyre and Jérôme Lelong. arXiv:1907.06; 094444 2019.
Neural network regression for bermudan option pricing.
Tuan Anh Le, Atilim Gunes Baydin, and Frank Wood. Inference compilation and universal probabilistic programming. In Artificial Intelligence and Statistics, pp. 1338 1338-1348. PMLR, 2017.
Michel Ledoux and Michel Talagrand. Probability in banach spaces. Springer- Verlag, 62:67-69 1991.
Daniel D. Lee and Н. Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems 18, pp. 556-562. 2001.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximale any function. Newral networks, 6(6):861 867, 1993.
Qiuwei Li, Zhihui Zhu, and Gongguo Tang. The non-convex geometry of low-rank matrix optimization. Information and Inference: A Journal of the IMA, 8(1):51-96) 2019.
21

---

Published in Transactions on Machine Learning Research (05/2023)
Zhouchen Lin, Risheng Liu, and Zhixun Su. Linearized alternating direction method with adaptive penalty for low-rank representation. In Advances in Neural Information Processing Systems 24, pp. 612 620. 2011.
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. SIAM J. Math. Anal., 53(5:544 5506, 2021. ISSN 0036-1410.
Gilles Meyer, Silvère Bonnabel, and Rodolphe Sepulchre. Regression on fixed-rank positive semidefinite matrices: A ricmannian approach. Journal of Machine Learning Research, 12(18):593-66) -22, 2011.
James R. Munkres. Topology- Prentice Hall, Inc., Upper Saddle River, NJ, 2000. ISBN 0-13-181629-2. Second edition of MR04641288.
James R. Munkres. Elements of algebraic topology. CRC Press, 2018.
Pranecth Narayanamurthy and Namrata Vaswani. Nearly optimal robust subspace tracking. In International Conference on Muchine Learning, pp. 3701-33 3709. PMLR, 2018.
Praneeth Netrapalli, Niranjan N, Sujay Sanghavi, Animashree Anandkumar, and Prateek Jain. Non- convex robust pea. In Advonces in Neural Information Processing Systems 27, pp. 1107-1115. 2014.
Duc Minh Nguyen, Evaggelia Tsiligianni, and Nikos Deligiannis. Matrix Factorization via Deep Learning, pp. 1rXiv:1812.01478 2018.
Riccardo Rebonato and Peter Jäckel. The most general methodology for creating a valid correlation matrix for risk management and option pricing purposes. Journal of Multivariate Analysis, 1998.
Paul Rodriguez and Brendt Wohlberg. Fast principal component pursuit via alternating minimization. pp. 69 73, 2013.
Reuven Y Rubinstein and Alexander Shapiro. Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method. Wiley, 1993.
Suvash Sedhain, Aditya Krishna Menon, Scott Sanner, and Lexing Xie. Autorec: Autoencoders meet collab- orative filtering. In Proceedings of the 24th International Conference on World Wide Web, pp. 111-112, 2015.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of ReLU networks in terms of width and depth. J. Moth. Pures Appl. (9), 157:101 135, 2022. ISSN 0021-7824.
Andrews Sobral, Thierry Bouwmans, and El-hadi Zahzah. Lislibrary: Low-rank and sparse tools for back- ground modeling and subtraction in videos. In Robust Low-Ramd and Sparse Matriz Decomposition: Applications in Image and Video Processing. CRC Press, Taylor and Francis Group 2015.
Oren Solomon, Regev Cohen, Yi Zhang, Yi Yang, Qiong He, Jianwen Luo, Ruud JG van Sloun, and Yonina C Eldar. Deep unfolded robust pea with application to clutter suppression in ultrasound. IEEE transactions on medical imaging, 3954) 1063, 2019.
Wang Song and Xia Shaowei. Robust pea based on neural networks. In Proceedings of the 36th IEEE Conference on Decision and Control, volume 1, pp. 503-508. IEEE, 1997.
George Trigeorgis, Konstantinos Bousmalis, Stefanos Zafeiriou, and Björn W. Schuller. A deep semi-nmi nmf model for learning hidden representations. In Proceedings of the 31st International Conference on Inter- national Conference on Machine Learning - Volume 32, pp. 11 1692 11 1700, 2014.
Stephen Willard. General topology. Addison Addison-Wesley Publishing Co., Reading, Loss-London-Doo Mills, Ont., 1970.
John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. In Advances in Neural Information Processing Systems 22, pp. 2009.
22

---

Published in Transactions on Machine Learning Research (05/2023)
Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust pea via outlier pursuit. In Advances in Newral Information Processing Systems 28, pp. 2990-2504. 2010.
Hong-Jian Xue, Xun-Yu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen. Deep matrix factorization models for recommender systems. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAP17, pp. 3203 2209, 2017.
Xinyang Yi, Dohyung Park, Yudong Chen, and Constantine Caramanis. Fast algorithms for robust pea via gradient descent. In Advances in Neural Information Processing Systems 29, pp. 4152-4160. 2016.
23


Reviews:
[{"review_id": "Ds5bRgVOAx", "reviewer": "Reviewer_CEtb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. My main consideration is the gap between theoretical analysis and optimization algorithm. The main theoretical Guarantees for Denise are based on the solution of the $\\ell_1$ regularized problem, while the training algorithm depends on some smooth approximation. I am not sure whether such approximation still hold the properties of Denise we desired. Especially, the non-smoothness of $\\ell_1$-norm plays an important role to obtain the sparsity. It is unclear whether the smoothing in training procedure is reasonable.\n\n2. Appendix A replaces $\\varphi_u$ by ${\\mathcal C}^2$ function while finding first-order stationary point by SGD only requires the objective function has Lipchitz continuous gradient. I hope the author could explain the benefit from such strong assumption on the approximation function.\n\n3. The real-world dataset used in Section 5.1 contains some 20-by-20 matrices, which is not large. I think applying deep learning model to train such small dataset is not interesting. Some empirical results on large-scale problems is desired.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a deep learning-based algorithm for robust PCA of covariance matrices which is called Denise. The authors provide some statistical properties of Denise and empirical studies on synthetic and real-world datasets to validate the proposed method.\n\n\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see above.", "broader_impact_concerns": "I think there is no broader impact concerns since this is a theoretical paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zV24vfnrJO", "reviewer": "Reviewer_uuQY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In Section 4, this paper presents the main universal approximation result to decompose a psd (positive semi-definite) matrix M into low-rank psd L + sparse matrix S using deep networks. I think this result is very interesting. However, it assumes that the training set follows an exact low-rank model such that the sparse part of the psd matrix S is zero (assumption 4.5). I think this assumption is quite strong, as it guarantees (theorem 4.6,4.7) that the deep learning model works if M = L, but it is not clear what happens if S is non-zero. More discussions are needed.\n\nIf I understood, these results are for the supervised training setup. It is still unclear what happens to the unsupervised fine-tuning setup. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a deep learning model to perform robust PCA which has a theoretical guarantee on its accuracy on positive semi-definite matrices. It is based on the universal approximation property of neural networks. It has the advantage to achieve a fast PCA computation on new matrices compared to existing state-of-the-art methods, while maintaining a similar accuracy. On practical data, supervised learning is first used to pre-train the deep learning model on synthetic data, and then unsupervised learning approach is used to fine-tune the model on practical data in order to achieve a good accuracy.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As mentioned in the introduction: … small perturbations lead to small changes in the output … I am not sure where you have presented these results, could you make this clearer?\n\nIs it possible to include the sparse term S in your assumption 4.5 so that you training data follows L+S?\n\nRegarding the numerical results, I think that you are assuming that you can estimate correctly the rank of the practical dataset in order to apply the supervised training approach, before performing unsupervised fine-tuning (beginning of section 5.1.1). It is not clear how you prepare the synthetic data with the correct rank, could you be more precise on this?\n\nMy last comment it to improve the quality of writing. What is the f* in Theorem 4.7? Is it the one in Assumption 4.5, or 4.4? I guess that it is the former. In Theorem 4.3, use Assumption 4.2 rather than Condition 4.2. Typo: train -> training dataset in the beginning of section 5, etc.\n\n", "broader_impact_concerns": "Overall, I think that there is still a gap between your theoretical results and numerical results. I would be good to improve these aspects in your revision.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1GB1sV4hfy", "reviewer": "Reviewer_ujHT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is an interesting submission which attempts to circumvent the algorithmic\nhardness of robust PCA by pre-training a deep neural network to produce the \ndecomposition.\nThis is in contrast to existing works, which use convex relaxations to compute\nthe decomposition.\nThe contributions of this work divide naturally into two areas: theoretical and empirical. \n\nOn the theory side, the main result is a universal approximation theorem \nshowing that neural networks can learn to generate (approximate) Cholesky \nfactorizations of arbitrary input matrices.\nThis topic is outside my research area and so I cannot comment on the \nnovelty of these results.\nThe major downside of the approximation theorems in my opinion is the requirement for exact \noptimization of the neural network model, which is NP-Hard in general.\nThe authors also provide an optimization guarantee for training Denise,\nbut this relies on a hard-to-justify assumption that the iterates remain in a compact\nset.\nAs a result, I feel this last contribution is negligible.\n\nOn the empirical side, the authors show Denise performs comparable to, or better than, existing\nconvex relaxations on both synthetic and real data. \nAlthough Denise tends to produce denser residuals matrices than PCP, its approximation\nerror is typically smaller so this may be acceptable to users.\nOne criticism I have here is that the time to compute the decomposition for \nDenise does not incorporate any of the training time for the neural network.\nThis training time is very significant. For example, the authors report eight \nhours of training for the synthetic dataset experiment.\nAdjusting for this training time (normalized by the test set) gives that\nDenise takes 2880 milliseconds per test example, which is much slower than its\ncompetitors.\n\nIt is possible to argue that Dense produces an inference artifact in the sense\nof inference compilation [1] and therefore the training time should not be\nincluded in the inference time.\nHowever, the network architecture is specific to the input size of the matrix and the\ndesired output rank, implying that Denise must be re-trained for each\nindividual dataset. \nAs a result, I argue that training time must be incorporated into the comparison\nin some fashion for it to be fair.\nAs is, I do not think the experiments in Tables 1-3 tell the whole story.\n\nTo summarize:\n\n**Strengths**:\n\n- The authors provide theoretical guarantees for Denise to recover \n    a solution function which computes robust PCAs (e.g. Cholesky factors with sparse residuals).\n- Denise performs comparably to or better than competing methods in terms of \n    approximation equality.\n- Denise allows for very fast inference when the underlying network is pre-trained. \n    \n\n**Weaknesses**:\n\n- Denise is slower than competing methods when adjusted for the time to train\n    the underlying neural network.\n- The optimization result (Theorem A.1) is not meaningful due to unrealistic assumptions. \n- Denise produces less sparse residual matrices than competitors.\n\n\n### Correctness\n\nI read through all of the proofs. I am confident Theorem 4.1 and Theorem A.1\nare correct as stated.\nTheorem 4.3 uses theoretical tools I am not familiar with and so I cannot \ncomment on it's correctness.\n\n\n### Writing and Presentation:\n\nThe paper is well written and the related work is thorough. I would suggest\nincluding references to \"inference compilation\" methods, since these\nwork on the same principle of pre-training training a neural network to do a\nslow/hard task quickly at test time. A good starting reference is Le, Baydin,\nand Wood [1].\n\nThere are a few places in the manuscript with awkward work choices (Assumption vs. Lemma) \nor where punctuation could be improved.\nSee \"Minor Comments\" below.\n\n\n#### Additional References:\n\n[1] Le, Tuan Anh, Atilim Gunes Baydin, and Frank Wood. \"Inference compilation and universal probabilistic programming.\" Artificial Intelligence and Statistics. PMLR, 2017.\n\n### Questions: \n\n- Theorem 4.6: This assumes (i) you can solve a non-convex optimization problem to global optimum; and (2) the depth of the network can be made arbitrarily large. How can users select the depth in practice, as well as deal with (potentially bad) local minima?\n- Section 5.1: \"symmetric positive semidefinite sparse matrix $S_0$\" --- But, if $S_0$ as symmetric positive-definite, then won't the unsupervised training method be realizable for this dataset? That is, $M = U U^\\top$ will hold for some $U$? I thought the only condition on $S_0$ was sparsity for this reason.\n- Section 5.1.1: \"computed low rank matrix L and the initial low rank matrix $L_0$,\" --- what does \"initial\" mean here? Do you mean the low-rank matrix from the synthetic train/test dataset? \n- Section 5.1.1: \"we approximately obtain a rank of 3 for matrices L\" --- By approximately do you mean that the result is not always rank $3$? That is, sometimes the rank is lower or higher? It seems like this would make a large difference for relative error. \n- Table 1: What are the numbers in parentheses? Are these standard deviations? If so, what are the taken over? The elements of the test set? Similarly, why is the rank not always an integral number for IALM and PCP? Were the ranks different for some elements of the test set (see question above) \n- Tables 1-3: It seems like all of the methods fail at recovering a sufficiently sparse residual matrix $S_0$. That is, $S$ is essentially dense for all the methods except for PCP. Why is that? Is it a thresholding problem? I would have hoped the $\\ell_1$ loss would produce more sparsity in the residual. \n\n#### Minor Comments\n\n- Abstract: \"current speed optimized method, fast PCP.\" --- it should be \"speed-optimized\", since this is a compound adjective.\n- Section 1: \"In particular, in Finance we need instantaneously\" --- there is no need to capitalize finance. \n- Section 2: \"is an computational improved version\" -> computationally\n- Section 2: \"In particular, The Fast Principal Component Pursuit\" --- there is no need to capitalize each word in the initialism. \n- Section 2: \"In (Herrera et al., 2020), the computation of\" --- use \"\\citet\" instead of \"\\citep\".\n- Section 2: \"Our work is similar to (Gregor & LeCun, 2010) in spirit\" --- same as previous. \n- Section 2: \"with their encoder, as continuity,\" --- maybe \"including\" instead of \"as\"?\n- Section 4.4: \"It is straight forward to see, that\" --- this comma is unnecessary. \n- Section 5: \"function on a synthetic train dataset\"  -> \"training\"\n- Section 5.1.1: \"dataset consisting of 10’000 matrices\" --- English orthography uses \"10,000\".\n- Assumption 4.4: I think this is meant to be \"Corollary 4.4\". \n- Section 7: \"guarantees, for the recovery\" --- this comma is unnecessary. \n- Appendix A: \"it is essential to know that this procedure does converge to a local minimum in our setting\" --- convergence to a stationary point (in expectation) as in Theorem A.1 does not guarantee the stationary point is a local minimum. \n- Assumption A.2: You typically make assumptions, rather than prove them. Is this supposed to be a Lemma? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes Denise, a deep-learning based method for robust principle\ncomponents analysis (PCA).\nRobust PCA is the problem of decomposing a matrix into the sum of a PSD matrix\nand a sparse matrix. \nDenise works by using a pre-trained deep neural network to output the Cholesky factor \nof the PSD matrix in the robust PCA decomposition given the matrix to decompose\nas input.\nPre-training can be supervised using real or synthetic data, or unsupervised\nwhen no robust PCA is available for the training data. \nThe authors develop several theoretical guarantees for their method:\nthey show that the robust PCA problem is well-posed --- there exists an almost-everywhere\ncontinuous solution function --- and that this solution function is recovered \nas the network becomes infinitely deep.\nThe paper concludes with experiments on real and synthetic data.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please incorporate training time for Denise into the time measurements for the experiments so that the comparison is fair.\n- Theorem A.1 should either be removed or it's unrealistic assumptions should be carefully discussed in the text. \n", "broader_impact_concerns": "I have no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewer uuQY mentioned an 1990s paper that may be relevant to the background; if this is appropriate, please include it in a minor revision.

The reviewers had a good discussion, with all four "Leaning Accept" in the end. Reviewer ujHT in particular championed the paper and argued that the novelty and technical contribution were significant; that because TMLR emphasizes "technical correctness over subjective significance", we should not judge the paper by whether the proposed method has immediate impact on practitioners.

After reading the paper myself, I concur with the reviewers. In particular, I thought the range of techniques in the proofs was impressive, and the results were non-trivial.  Hence I'm happy to recommend acceptance of the paper.
Decision: Accept (poster)