Year: 2021

Abstract:
Conventionally, the matrix completion (MC) model aims to recover a matrix from partially observed elements. Accurate recovery necessarily requires a regularization encoding priors of the unknown matrix/signal properly. However, encoding the priors accurately for the complex natural signal is difficult, and even then, the model might not generalize well outside the particular matrix type. This work combines adaptive and implicit low-rank regularization that captures the prior dynamically according to the current recovered matrix. Furthermore, we aim to answer the question: how does adaptive regularization affect implicit regularization? We utilize neural networks to represent Adaptive and Implicit Regularization and named the proposed model AIR-Net. Theoretical analyses show that the adaptive part of the AIR-Net enhances implicit regularization. In addition, the adaptive regularizer vanishes at the end, thus can avoid saturation issues. Numerical experiments for various data demonstrate the effectiveness of AIR-Net, especially when the locations of missing elements are not randomly chosen. With complete flexibility to select neural networks for matrix representation, AIR-Net can be extended to solve more general inverse problems.

heading: 1 INTRODUCTION
text: The matrix completion (MC) problem, which aims to recover a matrix X∗ ∈ Rm×n from its partially observed elements, has arisen in numerous domains, ranging from computer vision (Wen et al., 2012), recommender system (Netflix, 2009), and drug-target interaction (DTI) (Mongia & Majumdar, 2020). This fundamental problem is ill-posed without assumptions on X∗ since we have many completions. So it is essential to impose additional information or priors on the unknown matrix/signal.
To describe the prior for natural signal, or restrict the solution in the corresponding space is difficult. Classical methods for MC are mainly based on low-rank, sparsity or piece-wise smoothness assumption (Rudin et al., 1992; Buades et al., 2005; Romano et al., 2014; Dabov et al., 2007). These priors describe simple structural signal well, but may lead to a poor approximation of X∗ with complex structures (Radhakrishnan et al., 2021) especially when the observed entries are not sampled uniformly at random. Recently, deep neural networks (DNN) have shown a strong ability in extracting complex structures from large datasets(Li et al., 2018; Mukherjee et al., 2021). However, such a large number of data sets cannot be obtained in many scenarios. Fortunately, DNN also works in solving some inverse problems without any extra training set (Ulyanov et al., 2018). Over-parametric DNN performs well on a single matrix is a mysterious phenomenon. One of the explanations is there exists implicit regularization during training (Arora et al., 2019; Xu et al., 2019; Rahaman et al., 2019; Chakrabarty & Maji, 2019). Although DNN with implicit regularization outperforms some classical methods, it is insufficient to describe the space of complex X∗. Extra-explicit regularization can improve its performance in signal recovery (Metzler et al., 2018; Boyarski et al., 2019a; Liu et al., 2019; Li et al., 2020). However, such explicit priors are often valid only for specific data or sampling patterns. A more flexible regularization is required to meet practical MC problems.
We introduce flexibility in this paper by firstly representing the explicit regularization using DNN without any extra training set. The explicit regularization we begin with is Dirichlet Energy (DE), which is formulated as tr(X>LX), with L a Laplacian matrix describing the similarity between
columns. Note that L in DE is fixed during iteration. Building an exact L based on incomplete observation is very challenging. Therefore, we parameterize L with DNN, and revise L iteratively during training. Furthermore, We combine the learned DE, which is an adaptive regularizer, with implicit regularization to form a new regularization method for MC named AIR-Net. The interaction between explicit regularization and implicit regularization in solving MC problems is further studied. The results show that combining the two can obtain a new, more flexible regularization model and enhance the low-rank preference of implicit regularization. In many examples, AIR-NET has a more vital feature representation ability and more comprehensive application range and shows state-of-art performance.

heading: 2 ADAPTIVE AND IMPLICIT REGULARIZATION NEURAL NETWORK
text: Our model is proposed as follow:
min X,Wi Lall = LY (A (X∗) ,A(X)) + N∑ i=1 λi · RWi (Ti (X)) (1)
where A (X) = X |Ω= {
Xi,j , (i, j) ∈ Ω 0, (i, j) 6∈ Ω and Ω are the observed coordinates set, and the
other entries are missing. Different from other regularization models for MC, here X is represented by a neural network which tends to be low-rank implicitly (Section 2.1), and RWi is an adaptive regularization with a forward neural network represented Laplacian matrix(Section 2.2). The detailed notations will be introduced in the corresponding sections. A specific case of Equation 1 for matrix completion is given in Section 2.3.

heading: 2.1 DMF AS AN IMPLICIT REGULARIZATION
text: In order to make the model suitable for more matrix types, we need a more general data prior. The low-rank is a very general prior in various matrix types. There are two main ways to encode the low-rank prior into model: (a) Adding an explicit regularization term such as rank and nuclear norm (Candès & Recht, 2009; Lin et al., 2010). (b) Using a low-dimensional latent variable model to represent X , including matrix factorization (MF) and its varieties (Koren et al., 2009; Fan & Cheng, 2018). The first case suffers from the saturation issue, which is induced by explicit regularization. The second one faces the problem of estimating a proper latent variable dimension.
Unlike the existing MF model, which constricts the size of the shared dimension of the factorized matrix, DMF can take a large shared dimension and still preserve the low-rank property without explicit regularization. This is the so-called implicit low-rank regularization of DMF:
X(t) = W [L−1](t)W [L−2](t) . . .W [1](t)W [0](t) ∈ Rm×n, where L is the depth of MF. W [l](t) represents the l-th matrix at the step t during training. The results are given under a mild assumption 1 in Section A.2. This property helps avoiding dimension estimation and saturation issues. As for the details of the implicit low-rank we will discuss in Section A.2.

heading: 2.2 ADAPTIVE REGULARIZER
text: Apart from the low-rank prior, self-similarity is also a typical prior. The patch in the image and the rating behavior of users are all examples of self-similarity. For example, there is always a certain degree of self-similarity between the blocks in the image. A classical way to encode the similarity prior to X is Dirichlet Energy (DE) which is formulated as tr(X>LX). But DE will face two problems in applications: (a) L is unknown in MC problem, construct L based on incomplete X may induce worse prior. (b) The formulation of DE only encodes the similarity of the columns of X . Other similarities such as block similarity cannot be captured. To address both of these issues, we parameterize L with DNN and replace X by a transformed Ti (X) to capture the self-similarity flexibly.
The adaptive regularization is defined as RWi (Ti (X)) = tr ( Ti (X)>Li (Wi) Ti (X) ) , i = 1, 2, . . . , N
where Li ∈ Rmi×mi is parameterized by Wi ∈ Rmi×mi . To keep the Laplacian properties of Li, special design for the parameterized structure is important. We design a forward neural network which encodes the properties of Laplacian matrix in structure. The details are discussed in A.4. Ti : Rm×n 7→ Rmi×ni transforms X into special domain, which makes the AIR-Net possible to capture various relationships embedded in data. The common choice can be Ti (X) = X which captures the relationship between columns. Regularization captures the relationship between rows when Ti (X) = X>. Especially if Ti(X) =[ vec (block(X))1 , vec (block(X))2 , . . . , vec (block(X))ni ] , where vec (block(X))j ∈ Rmi is the vectorization of j-th block in X row by row, then the similarity among blocks can be obtained. A natural problem that arises is what the Li looks like during training.
Obviously, RWi reaches minimum when Li = 0, and this is called a trivial solution. The most exciting thing is that when we minimize Equation 1 with the gradient descent algorithm, {Li(Wi(t))} converges to a non-trivial solution. Another expected phenomenon is that RWi vanishes at the end and will not cause the so-called saturation issue. The saturation issue is a bias term that dominates the overall estimation error due to explicit regularization. We illustrate these phenomena both by theoretical analysis (Theorem 2 in Section 3.2) and numerical experiments (Section 4).

heading: 2.3 AIR-NET FOR MC
text: In this subsection, we will focus our model on the MC problem. We select T1 (X) = X , T2 (X) = X>, N = 2 to capture the relationship both in rows and columns of X . Overall, the theoretical analyses for general inverse problem is based on Equation 2.
min X,W r,W c
Lall = LY (A (X∗) ,A (X)) + λr · RWr (X) + λc · RWc ( X> ) , (2)
where X = W [L−1]W [L−2] . . .W [1]W [0], RWr (X) = XLr(Wr)X>, RWc ( X> ) = X>Lc(Wc)X . Specially, our experiments focus on the MC problem which can reform Equation 2 as follows:
min W [l],W r,W c
Lall = ∑
(i,j)∈Ω ∣∣Xij −X∗ij∣∣+ λr · RWr (X) + λc · RWc (X>) , (3) with l = 0, 1, · · · , L − 1. The parameters in Equation 3 is updated by gradient descent algorithm or its variations. We stop the iteration until
∣∣RWr(T+1) −RWr(T )∣∣ < δ and∣∣RWc(T+1) −RWc(T )∣∣ < δ. The recovered matrix is X̂(T ) = W [L−1](T ) · · ·W [0](T ). Some works which combine implicit and explicit regularization also can be regarded as a special case of Equation 1. Both the Total Variation (TV) and DE can be regarded as a fixed L. Therefore, the framework of Equation 1 also contains DMF+TV (Li et al., 2020), DMF+DE (Boyarski et al., 2019a). So far, we cannot see any essential difference between Equation 3 and these models. We will illustrate the amazing properties of the model in the next section.

heading: 3 THEORETICAL ANALYSIS
text: In this section, we will analyze the properties based on the dynamics of Equation 3. Theorem 1 shows that our proposed regularization enhances the implicit low-rank regularization of DMF. Theorem 2 shows that the adaptive regularization will converge to a minimum while capturing the inner structure of data flexibly. Although this paper focus on MC problem, the following theoretical analyzes is satisfied for the general inverse problems. As A and A (X∗) are fixed during optimization, we simplify LY (A (X∗) ,A (X)) as LY (X) below. Ui,j is the (i, j) th entry of U , U:,k and Uk,: are the k-th column and the k-th row of U respectively.

heading: 3.1 AIR-NET ENHANCES THE IMPLICIT LOW-RANK REGULARIZATION
text: To simplify the analysis, we keep Lr and Lc fixed. Then theRWi , i = r, c only varies with X . We will demonstrate what the adaptive regularizer brings to the implicit low-rank regularization.
Theorem 1. Consider the following dynamics with initial data satisfying the balance initialization Assumption 1(see A.2):
Ẇ [l](t) = − ∂ ∂W [l] Lall(X(t)), t ≥ 0, l = 0, . . . , L− 1,
where Lall (X) = LY(X) + λr · RWr (X) + λc · RWc (X). Then for k = 1, 2, . . ., we have
σ̇k(t) =− L ( σ2k(t) )1− 1L 〈∇WLY(X(t)),U:,k(t)V >:,k(t)〉 − 2L ( σ2k(t) ) 3 2− 1 L γk(t),
(4)
where X(t) = U(t)S(t)V >(t) is the SVD for X (t), W = [ W [0],W [1], . . . ,W [L−1] ] , X =∑
s σsU:,sV
> :,s , γk(t) = U > :,kLrU:,k + V > :,kLcV:,k ≥ 0.
Proof. Directly calculate the gradient of Lall at W and utilize Equation 4 will obtain the result. The details of proof can be found in A.3.
Compared with the results of vanilla DMF whose order of σk(t) is 2 − 2L . This Theorem demonstrates that AIR-Net’s σk(t) has a higher dynamics order which is 3 − 2L . Notice that the adaptive regularizer keeps γk(t) ≥ 0. In this way, a bigger convergence speed gap appears between different singular values σr than vanilla DMF. Therefore, the AIR-Net enhances the implicit tendency of DMF toward low-rank.

heading: 3.2 THE DYNAMICS OF ADAPTIVE REGULARIZER
text: Now suppose X is given and fixed. We focus on the converge property of RTi(W ) based on the evolutionary of the dynamics of Li. RTi(W ) vanishes at the end and avoids AIR-Net suffering from saturation issues.
Theorem 2. Consider the gradient flow model, where ∥∥∥Ti (X)k,:∥∥∥2
F = 1 and Ti (X)k,l > 0. If we
initialize Wi (0) = ε1mi×mi , then W (t) will keep symmetric during optimization. We can get the following element-wise convergence relationship∣∣∣Li(k,l)(t)−L∗i(k,l)∣∣∣ ≤ { (mi + 2ki) · exp(−D · t), (k, l) ∈ C1
exp (−D · t) , (k, l) ∈ C2 (mi − 1) · (mi + 2ki) exp(−D · t), k = l
where C1 = { (k, l) | k 6= l, Ti (X):,k 6= Ti (X):,l } , C2 = { (k, l) | k 6= l, Ti (X):,k = Ti (X):,l } ,
L∗i(k,l) =  0, (k, l) ∈ C1 γ, (k, l) ∈ C2 − ∑mi
l′=1,l′ 6=l L ∗ i(k,l′), k = l
Li(k,l)(t) is (k, l)-th the element of Li(t), 1mi×mi is a matrix of all-one. γ = 2 |{Ck̂,l̂=0}| = 2mi+2ki ,

heading: D is a constant defined in A.4 which equals to zero if and only if X = 1mi×ni .
text: Proof. We prove this theorem in A.4.
This Theorem gives the limit point L∗ and convergence rate of Li(t). (k, l) ∈ C1 L∗i (k, l) = 0. unless Ti (X):,k = Ti (X):,l or k = l, that is to say, in the end, L∗i will only think that the exact same columns in Ti (X) are related. Li(k,l)(t) converges faster when (k, l) ∈ C2 than (k, l) ∈ C1. In another word, adaptive regularizer captures the similarity first. This convergence rate gap products a multi-scale similarity which will be discussed in Section 4.1. Additionally, it’s not difficult to find RW ∗i = 0, the convergence rate is given as follow: Corollary 1. In the setting of Theorem 2, we further have 0 ≤ RWi(t) ≤ 2 (mi + 2ki) (mi − 1)mi · exp(−Dt), i = 1, 2, . . . , N .
Proof. We prove this theorem in appendix A.5.
According to Corollary 1, lim t→+∞ RWi(t) → 0. Therefore, the regularization will vanish at the end and not induce the saturation issue.
Remark 1. Notice that we have no restriction on specific Ti,A or representation of X in the above proof. Therefore, the conclusion in this subsection is a general result for inverse problem.
In this subsection, we demonstrate AIR-Net’s fantastic theoretical properties. It can both enhance the implicit low-rank and avoid saturation issues. We will verify these properties and the effectiveness of AIR-Net in applications experimentally.

heading: 4 EXPERIMENTAL ANALYSIS
text: Now we demonstrate the adaptive properties of AIR-Net by numerical experiments: (a) Lr and Lc capture the structural similarity in data from large scale to small scale (Section 4.1); (b) The comprehensive similarity in all scales contribute to successful MC, therefore the adaptive regularizer is necessary (Section 4.2); (c) Because AIR-Net is adaptive to data, it avoids over-fitting and achieves good performance. (Section 4.3).
Data type and sampling pattern Three types of matrices are considered: gray-scale image, usermovie rating matrix, and drug-target interaction (DTI) data. Three standard test gray images of size 240 × 240(Monti et al., 2017) are included in the image type (Baboon, Barbara, and Cameraman). The user-movie rating matrix is Syn-Netflix which is of 150× 200, and the DTI data has Ion channels (IC) and G protein-coupled receptor (GPCR) are shaped 210 × 204 and 223 × 95 respectively (Boyarski et al., 2019b; Mongia & Majumdar, 2020). The sampling patterns include random missing, patch missing and textural missing, which are listed in Figure 4. The random missing rate varies in different experiments, and the default is 30%.
Parameter settings We set λ = µ = X ∗ max−X ∗ min
mi·ni to ensure the fidelity and the regularization are in the same order of magnitude, where X∗max and X ∗ min are maximum and minimum of X
∗. The δ is a threshold which we set as mn1000 by default. All the parameters in AIR-Net are initialized with Gaussian distribution, which owns zero mean and 10−5 as its variance. The Adam is chosen as the optimization algorithm by default (Kingma & Ba, 2015).

heading: 4.1 AIR-NET CAPTURE RELATIONSHIP ADAPTIVE TO BOTH SPATIAL AND TIME DOMAIN
text: In this section, we will verify the previously proposed theorems. This section provides a few slices of Lr and Lc during training to demonstrate what AIR-Net can learn. The heatmap of Lr(t) and Lc(t) for Baboon at t = 4000, 7000, 10000 respectively are shown in Figure 1. The according results for Syn-Netflix are shown in Figure 5 in A.1. The first row shows the heatmap of Lr(t) and the second one shows the heatmap of Lc(t).
As Figure 1 shows, both Lr(t) and Lc(t) first appear many blocks (t = 4000). Specially, we sigh two of Lc(t = 4000) out. These blocks indicate that these corresponding blocks columns are highly related. These blocks correspond to columns in which the eyes of Baboon are located, which are indeed highly similar. However, the slight difference between these columns induces the relationship captured by adaptive regularizer focusing on the related columns (t = 7000), which is similar to TV(Rudin et al., 1992). The columns of Baboon are not fully the same. The regularization gradually vanishes (t = 10000), which matches the results of Theorem 2 (Figure 1). Except the gray-scale images, the results on Syn-Netflix give similar conclusion.
These results illustrate that AIR-Net captures the similarity from large scale to small scale. Meanwhile, a natural question is raised: does there exist a moment that both Lr and Lc are captured accurately? If yes, we can train AIR-Net with these fixed Lr and Lc to obtain better recovery performance. The experiments below show that the Lr and Lc captured by AIR-Net are necessary for MC.

heading: 4.2 THE NECESSITY OF UTILIZING AN ADAPTIVE REGULARIZER
text: In this section, the necessity of adaptive updating Lr and Lc is explored. Let AIR-Net have a fixed regularizer, which is an adaptive regularizer learned at a specific step. The Normalized Mean Absolute Error (NMAE) is adopted to measure the distance between the recovered matrix X̂ and the actual matrix X∗:
NMAE = 1 (X∗max −X∗min) |Ω̄| ∑
(i,j)∈Ω̄ ∣∣∣X̂ij −X∗ij∣∣∣ , where Ω̄ is the complement set of Ω. We utilize the regularization captured by AIR-Net at t = 4000, 7000, 9000 respectively. All of the training hyper-parameters keep the same as AIR-Net. The Baboon under all the three missing patterns are tested.
Figure 2 shows how the NMAE changes with the epoch of training. AIR-Net, which updates the regularization during training, achieves the best performance in all missing patterns. The fixed regularization can accelerate the convergence speed of the algorithm. In random missing case,RWr (9000) and RWc(9000) is the best fixed regularizer among three time steps while other missing cases are RWr (7000) and RWc(7000). Fixed regularizer based methods will face two problems: (a) How to determine the best step? (b) How to estimate the regularization based on the partially observed matrix before training? These problems are not easy to solve. AIR-Net solves these problems from another perspective by updating the regularization during training. The adaptive property of AIRNet is essential to the effectiveness of AIR-Net.

heading: 4.3 AIR-NET ADAPTIVE TO BOTH VARIES DATA AND MISSING PATTERN
text: Now we apply AIR-Net for matrix completion on three data types under different missing patterns.
Peered methods The peered methods include KNN(Goldberger et al., 2004), SVD(Troyanskaya et al., 2001), PNMC(Yang & Xu, 2020), DMF(Arora et al., 2019) and RDMF(Li et al., 2020) in image type. Here RDMF is replaced by DMF+DE(Boyarski et al., 2019a) because it is more suitable in the Syn-Netflix experiment.
Avoid Over-fitting. Figure 3 shows how the NMAE of DMF and AIR-Net changes with the training step. Compared with vanilla DMF, AIR-Net avoids over-fitting and achieves better performance on
all the three data types and missing patterns. The Syn-Netflix and DIT data can be found in Figure 6 at A.1.
Adaptive to data. Our proposed method achieves the best-recovered performance in most tasks. Table 1 shows the efficacy of AIR-Net on the various data types. More surprising is that our methods perform better than other methods, which are well designed for the particular data type. The recovered results are shown in Figure 4. In this figure, the existing methods perform well on specific missing pattern data. Such as the RDMF achieved good performance on the random missing case but performed not OK on reminding missing patterns. PNMC completed the patch missing well while obtaining worse results on texture missing. Thanks to the proposed model’s adaptive properties, our method achieves promising results both visually and by numerical measures.

heading: 5 CONCLUSION
text: We have proposed AIR-Net which aims to solve the MC problem without knowning the prior in advance. We show that our AIR-Net can adaptively learn the regularization according to different data at different training steps. In addition, we demonstrate that AIR-Net can avoid the saturation issue and over-fitting issue simultaneously. In fact, the AIR-Net is a general framework for solving the inverse problem. In the future work, we will combine other implicit regularization such as FPrinciple(Xu et al., 2019) with more flexible Ti for other inverse problems.

heading: A APPENDIX
text: A.1 EXPERIMENTS RESULTS
In this section, we place the experiments mentioned before. Figure 5 shows the heatmap of Lr and Lc learned by adaptive regularizer. Eventually, adaptive regularizer obtain the Lr and Lc which are highly similar to real L̂r and L̂c in first column.
Figure 6 shows the NMAE of Syn-Netflix, IC and GPCR during training, respectively. This experiment result also shows the ability to avoid over-fitting.
A.2 INTRODUCTION OF DMF
Assumption 1. Factor matrices are balanced at initialization, i.e.,
W [l+1] > (0)W [l+1](0) = W [l](0)W [l] > (0), l = 0, . . . , L− 2.
Under this assumption, Arora et al. studied the gradient flow of the non-regularized risk function LY, i.e.,
Ẇ [l](t) = − ∂ ∂W [l] LY (X(t)) , t ≥ 0, l = 0, . . . , L− 1, (5)
where the empirical risk LY can be any analytic function of X(t). According to the analyticity of LY, X(t) has the following singular value decomposition where each matrix is an analytic function of t:
X(t) = U(t)S(t)V >(t),
where U(t) ∈ Rm,min{m,n},S(t) ∈ Rmin{m,n},min{m,n}, and V (t) ∈ Rmin{m,n},n are analytic functions of t; and for every t, the matrices U(t) and V (t) have orthonormal columns, while S(t) is diagonal (its diagonal entries may be negative and may appear in any order). The diagonal entries of S(t), which we denote by σ1(t), . . . , σmin{m,n}(t), are signed singular values of X(t). The columns of U(t) and V (t), denoted by U1(t), . . . ,Umin{m,n}(t) and V1(t), . . . ,Vmin{m,n}(t), are the corresponding left and right singular vectors respectively. Based on these notation, Arora derive the following singular values evolutionary dynamics equation. Proposition 1 ((Arora et al., 2019, Theorem 3)). Consider the dynamics Equation 5 with initial data satisfying Assumption 1. Then the signed singular values σk(t) of the product matrix X(t) evolve by:
σ̇k(t) = −L ( σ2k(t) )1− 1L 〈∇XLY(X(t)),U:,k(t)V >:,k(t)〉 , k = 1, . . . ,min {m,n} .
(6)
If the matrix factorization is non-degenerate, i.e., has depth L ≥ 2, the singular values need not be signed (we may assume σk(t) ≥ 0 for all t ).
Arora et al. claimed the terms ( σ2k(t) )1− 1L enhance the movement of large singular values, and on the other hand, attenuate that of small ones. The enhancement/attenuation becomes more significant as L grows.
A.3 PROOF OF THEOREM 1
We first give the details of the proposed adaptive regularizer with a iterative definition: RWi (Ti (X)) = tr ( Ti (X)>LiTi (X) ) Li = (A ∗ i · 1mi×mi) Imi −A∗i A∗i = Ai (1mi×mi − Imi)
Ai = exp(Wi + W
> i )
‖exp(Wi)‖1
,
Theorem 1. Consider the following dynamics with initial parameters satisfying Assumption 1:
Ẇ [l](t) = − ∂ ∂W [l] Lall(X(t)), t ≥ 0, l = 0, . . . , L− 1,
where Lall (X) = LY(X) + λr · RWr (X) + λc · RWc (X). Then we have for any k = 1, 2, . . . σ̇k(t) =− L ( σ2k(t) )1− 1L 〈∇WLY(X(t)),U:,k(t)V >:,k(t)〉 − 2L ( σ2k(t) ) 3 2− 1 L γk(t),
where X(t) = U(t)S(t)V >(t), X = ∑ s σsU:,sV > :,s , γk(t) = U > :,kLrU:,k + V > :,kLcV:,k ≥ 0.
Proof. This is proved by direct calculation: ∇W (λr · Rr + λc · Rc) = ∂tr ( λr ·X>LrX + λc ·XLcX> ) ∂X
= 2λr ·LrX + 2λc ·XLc = 2λr ·Lr ∑ s σsU:,sV > :,s + 2λc · ∑ s σsU:,sV > :,sLc.
Note that
〈V:,s,Vs′〉 = 〈U:,s,Us′〉 = δss′ = { 1, s = s′, 0. s 6= s′.
Therefore
U>:,k (∇W (λr · Rr + λc · Rc))V:,k = 2σk(λr ·U>:,kLrU:,k + λc · V >:,kLcV:,k) = 2σkγk(t),
where the term γk(t) = 2σk(λr · U>:,kLrU:,k + λc · V >:,kLcV:,k) ≥ 0. Furthermore, according to Equation 6, we have U>:,k∇WLYV:,k = −L ( σ2k(t) )1− 1L 〈∇WLY(X(t)),U:,k(t)V >:,k(t)〉. Finally, according to Ẇ [l](t) = − ∂
∂W [l] Lall(X(t)), we have
σ̇k(t) = −L ( σ2k(t) )1− 1L 〈∇WLY(X(t)),U:,k(t)V >:,k(t)〉− 2L (σ2k(t)) 32− 1L γk(t).
A.4 PROOF OF THEOREM 2
Proposition 2. ∇Wi (RWi (X)) = 2C Ai − 2tr (CA′i)A′i, where A′i = exp(Wi) ‖exp(Wi)‖1 , Ai = A′i + A ′ i > and C = 1mi×mi · ( Ti (X) Ti (X)> Imi ) − Ti (X) Ti (X)>.
Proof. We denote X = Ti (X) ∈ Rmi×ni , then we consider d [ tr ( X>LiX )] d [ tr ( X>LiX
)] =tr [ d ( LiXX
>)] =tr [ (dAi (1mi×mi − Imi) · 1mi×mi) In ·XX>
−dAi (1mi×mi − Imi)XX> ]
=tr [( XX> )> (Imi (dAi (1mi×mi − Imi) · 1mi×mi))
− ( XX> )> ((1mi×mi − Imi) dAi) ] =tr [( XX> Imi )> dAi (1mi×mi − Imi) · 1mi×mi
− ( XX> (1mi×mi − Imi) )> dAi ] =tr [(( XX> Imi ) 1mi×mi )> (dAi (1mi×mi − Imi))
− ( XX> (1mi×mi − Imi) )> dAi ] =tr [((( XX> Imi ) · 1mi×mi ) (1mi×mi − Imi)− ( XX> (1mi×mi − Imi) )>) dAi
] =tr [(( XX> Imi ) 1mi×mi −XX> ) dAi ]
We denote C = ( XX> Imi ) 1mi×mi −XX>, SWi = 1>mi · exp (Wi) · 1mi , then
d [ tr ( X>LiX )] =tr (CdAi)
= 1 S2Wi tr [ C ( SWi · exp(Wi + W>i ) d(Wi + W>i ) ) −C ( 1>mi (exp(Wi) dWi)1mi ) exp(Wi + W > i ) ]
=tr [ C · ( Ai d ( Wi + W > i ))] − 1 S2Wi tr [1mi×mi (exp(Wi) dWi)] · tr [ C · exp ( Wi + W > i
)] =tr [ C · ( Ai d ( Wi + W > i
))] − 1 S2Wi tr [(1mi×mi exp(Wi)) dWi] · tr [ C · exp ( Wi + W > i
)] =tr [ C · ( Ai d ( Wi + W > i ))] − tr [tr (C ·Ai) ·A′idWi]
=tr [(( C> Ai )> + C> Ai − tr (C ·Ai)A′i ) dWi ] Therefore,
∇Witr ( X>LiX ) = ( C> Ai )> + C> Ai − tr (C ·Ai)A′i
= 2C Ai − 2tr (CA′i)A′i Notice that X = Ti (X) ∈ Rmi×ni , the proposition is proved.
Theorem 2. Consider the gradient flow model, assume ∥∥∥Ti (X)k,:∥∥∥2
F = 1 and Ti (X)k,l > 0, if we
initialize Wi (0) = ε1mi×mi , then W (t) will keep symmetric during optimization. We can get the element-wise convergence relationship∣∣∣Li(k,l)(t)−L∗i(k,l)∣∣∣ ≤ { (mi + 2ki) · exp(−D · t), (k, l) ∈ C1
exp (−D · t) , (k, l) ∈ C2 (mi − 1) · (mi + 2ki) exp(−D · t), k = l
where C1 = { (k, l) | k 6= l, Ti (X):,k 6= Ti (X):,l } , C2 = { (k, l) | k 6= l, Ti (X):,k = Ti (X):,l } ,
L∗i(k,l) =  0, (k, l) ∈ C1 γ, (k, l) ∈ C2 − ∑mi
l′=1,l′ 6=l L ∗ i(k,l′), k = l
Li(k,l)(t) is the element of Li(t) at the k-th row and l-th column, 1mi×mi is all one elements matrix. γ = 2|{Ck̂,l̂=0}| = 2mi+2ki , D is a constant defined in A.4 which equals to zero if and only if X = 1mi×ni .
Proof. We rewritten the gradient in proposition 2 with element wise formulation:
ẆTi(k,l) (t) = (2Ca(t)− 4Ck,l) ·A ′ i(k,l)(t),
where Ca(t) = tr (CA′i) and the sub index denote the element in matrix. With the assumption that ∥∥∥Ti (X)k,:∥∥∥2
F = 1 and Ti (X)k,l > 0, we have 0 ≤( Ti (X) Ti (X)> ) k,l ≤ 1. Therefore Ck,l = ( Ti (X) Ti (X)> ) k,k − ( Ti (X) Ti (X)> ) k,l ≥ 0 and specially Ck,k = 0, as A′i(k,l) = exp(Wik,l)
‖exp(Wi)‖1 > 0, we have
Ca(t) = tr (CA′i) = mi∑ k=1,l=1 Ck,lA ′ i(k,l)(t) > 0
Denote Ck̂,l̂ ∈ mink,l Ck,l, we have Ck̂,l̂ ≤ Ck,l and then consider
ẆTi(k̂,l̂)(t)− ẆTi(k,l)(t) = 2Ca(t) ( A′
i(k̂,l̂) (t)−A′i(k,l)(t)
) − 4 ( Ck̂,l̂A ′ i(k̂,l̂) (t)−Ck,lA′i(k,l)(t) )
As we initialize Wi (0) = ε1mi×mi , therefore A ′ i(k,l)(0) = 1 m2i ,∀k, l. Therefore ẆTi(k̂,l̂)(0) − ẆTi(k,l)(0) = −4 ( Ck̂,l̂ −Ck,l ) A′i(k,l)(0) = −
4 m2i
( Ck̂,l̂ −Ck,l ) ≥ 0. Then we have
WTi(k̂,l̂)(t) ≥ WTi(k,l)(t) and A ′ i(k̂,l̂) (t) ≥ A′i(k,l)(t), the equal is token if and only if t = 0 or Ck̂,l̂ = Ck,l. Furthermore, ẆTi(k̂,l̂)(t) − ẆTi(k,l)(t) ≥ −4 ( Ck̂,l̂ −Ck,l ) A′i(k,l)(0), then
WTi(k̂,l̂)(t)−WTi(k,l)(t) ≥ Dk̂,l̂,k,l · t, where Dk̂,l̂,k,l = −4 ( Ck̂,l̂ −Ck,l ) A′i(k,l)(0) ≥ 0. Next, we consider
A′ i(k̂,l̂) (t) = exp(Wi(k̂,l̂))∥∥exp(WTi(k,l))∥∥1
= exp(Wi(k̂,l̂))∑
k,l
exp(WTi(k,l)) = 1∑ k,l exp(WTi(k,l) −WTi(k̂,l̂))
≥ 1∑ k,l exp ( −Dk̂,l̂,k,l · t ) As Ck,k = 0 and Ck,l ≥ 0, therefore Ck,k ∈ min
k,l Ck,l=0. It is not difficult to show that Ck̂,l̂ = 0 if and only if Ti (X):,k̂ = Ti (X):,l̂. If ∣∣∣{Ck̂,l̂ = 0}∣∣∣ = mi + 2ki, then when Ck̂,l̂ = 0, A′i(k̂,l̂) (t) ≥ 1 mi+2ki+Ek̂,l̂(t) , where Ek̂,l̂ (+∞) = 0. Notice that ∑ k,l A′i(k,l) (t) = 1, we have
1
mi + 2ki + Ek̂,l̂(t) ≤ A′ i(k̂,l̂) (t) ≤ 1 mi + 2ki
Therefore, A′ i(k̂,l̂)
(+∞) = {
0 , Ti (X):,k 6= Ti (X):,l 1 mi+2ki , Ti (X):,k = Ti (X):,l . Furthermore, Ai(k̂,l̂) =
2A′ i(k̂,l̂) = 2mi+2ki = γ, Ai(k,l) (+∞) = { 0 , Ti (X):,k 6= Ti (X):,l γ , Ti (X):,k = Ti (X):,l . According to the definition of Li,
L∗i(k,l) = Li(k,l)(t)(+∞) =  0 k 6= l, Ti (X):,k 6= Ti (X):,l γ k 6= l, Ti (X):,k = Ti (X):,l − ∑mi
l′=1,l′ 6=k L ∗ i(k,l′) k = l
Until now, we have prove that the adaptive regularization part of AIR-Net will convergence at the end. That is the upper bound of ∣∣∣L∗i(k,l) −Li(k,l)(t)∣∣∣. Next we will focus on the convergence rate of AIR-Net. We discuss the rate under the three cases in the aforementioned formulation separately. We simplify the notation furthermore before continue. C1 ={ (k, l) | k 6= l, Ti (X):,k 6= Ti (X):,l } , C2 = { (k, l) | k 6= l, Ti (X):,k = Ti (X):,l } . Then the formulation is simplified as
L∗i(k,l) =  0 (k, l) ∈ C1 γ (k, l) ∈ C2 − ∑mi
l′=1,l′ 6=k L ∗ i(k,l′) k = l
If (k, l) ∈ C2 or k = l, we denote D = minDk,l, according to the definition of Ek,l(t), we have Ek,l(t) ≤ exp(−D · t)∣∣∣A∗i(k,l) −Ai(k,l)(t)∣∣∣ = 2 [ 1mi + 2ki − 1mi + 2ki + Ek,l(t) ] ≤ 2 Ek,l(t)
(mi + 2ki) 2
≤ 2 · mi(mi−1) 2 · exp(−D · t) (mi + 2ki) 2
≤ exp (−D · t) Specially, when (k, l) ∈ C2 we have∣∣∣L∗i(k,l) −Li(k,l)(t)∣∣∣ = ∣∣∣A∗i(k,l) −Ai(k,l)(t)∣∣∣ ≤ exp (−D · t) If (k, l) ∈ C1,∣∣∣L∗i(k,l) −Li(k,l)(t)∣∣∣ = ∣∣∣A∗i(k,l) −Ai(k,l)(t)∣∣∣ = ∣∣Ai(k,l)(t)∣∣
≤ ∣∣∣∣∣∣ ∑
(k′,l′)∈C1∪sC3
Ai(k′,l′)(t) ∣∣∣∣∣∣ = ∣∣∣∣∣∣2− ∑
(k′,l′)∈C2∪C3
Ai(k′,l′)(t) ∣∣∣∣∣∣ = ∣∣∣∣∣∣γ · (mi + 2ki)− ∑
(k′,l′)∈C2∪C3
Ai(k′,l′)(t) ∣∣∣∣∣∣ = ∣∣∣∣∣∣ ∑
(k′,l′)∈C2∪C3
( γ −Ai(k′,l′)(t) )∣∣∣∣∣∣ ≤
∑ (k′,l′)∈C2∪C3 ∣∣γ −Ai(k′,l′)(t)∣∣ =
∑ (k′,l′)∈C2∪C3 ∣∣∣A∗i(k′,l′) −Ai(k′,l′)(t)∣∣∣ ≤ (mi + 2ki) · exp(−D · t) If k = l,∣∣∣L∗i(k,l) −Li(k,l)(t)∣∣∣ = ∣∣∣∣∣∣ mi∑
l′=1,l′ 6=k
( L∗i(k,l′) −Li(k,l′)(t) )∣∣∣∣∣∣ ≤ (mi − 1) · (mi + 2ki) · exp(−D · t)
A.5 PROOF OF COROLLARY 1
Corollary 1. In the setting of Theorem 2, we further have 0 ≤ RWi(t) ≤ 2 (mi + 2ki) (mi − 1)mi · exp(−Dt).
Proof. RWi(t) = ∑ k,l Li(k,l)(t)(t) ‖Ti(X):,k − Ti(X):,l‖ 2 F
≤ 2 · ∑ k 6=l Li(k,l)(t)(t) ≤ mi (mi − 1) (mi + 2ki) · exp(−Dt)

Review summaries:
This paper studies the problem of matrix completion using neural networks and deep matrix factorization as implicit and explicit regularization. The paper proposes a general framework and studies a specific case, namely, when the regularization is a form of Dirichlet Energy on the rows and columns of the matrix, and the matrix is formed as a product of L matrices. The results indicate improved performance of matrix completion under a variety of corruption methods and for a number of data sets. 

This paper studies the matrix completion problem where the goal is to recover the matrix from partially observed elements.  The proposed approach involves parameterizing the unknown matrix by deep matrix factorization and adaptive regularizers that are parameterized with deep neural networks. The authors studied the Adaptive and Implicit Regularization of the proposed approach which is called AIR-Net. Experiments are provided to demonstrate the effect of the proposed approach. 

In this manuscript, the authors consider matrix completion problems. Leveraging recent advances on implicit regularization in (deep) matrix factorization problems, a new architecture for matrix completion is proposed. Specifically, the authors parameterize the unknown low-rank matrix as a deep linear network, which has been shown to exhibit a low-rank bias when learned via gradient descent. Additional regularization terms based on the Dirichlet energy are added to encourage other structural priors in the recovered solution, such as self-similarity between columns or blocks. The underlying Laplacian matrix is parameterized by learnable weights. The authors analyze the dynamics of gradient flow applied to their optimization problem and show empirically that this approach improves performance in certain settings.

This paper proposes a generalization and extension to deep matrix factorization as presented in the former paper from [Arora et al, NeurIPS 2019]. The extension allows more complex model which include inverse problems. The generalization part is build on a "vanishing" regularization which leads to better dynamics and convergence. These results are given by a theoretical analysis which highlight the effect of the proposed model. Finally the experiments illustrate the advantage of the model compared to state-of-art methods.