Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Authors: Gengshuo Chang
Wei Zhang
Lehan Zhang
Venue: ICML 2025 poster (2025)
Keywords: matrix completion
side information
PAC learning theory
orthogonal complement projection
Primary area: theory->optimization
TL;DR: We propose OCMC, a matrix completion method that effectively leverages incomplete side information and outperforms existing methods on synthetic and real-world data.

Abstract: Matrix completion aims to recover missing entries in a data matrix using a subset of observed entries. Previous studies show that side information can greatly improve completion accuracy, but most assume perfect side information, which is rarely available in practice.   In this paper, we propose an orthogonal complement matrix completion (OCMC) model to address the challenge of matrix completion with incomplete side information. The model leverages the orthogonal complement projection derived from the available side information,   generalizing the traditional perfect side information matrix completion to the scenarios with incomplete side information.  Moreover, using probably approximately correct (PAC) learning theory, we show that the sample complexity of OCMC model decreases quadratically with the completeness level. To efficiently solve the OCMC model, a linearized Lagrangian algorithm is developed with convergence guarantees. Experimental results show that the proposed OCMC model outperforms state-of-the-art methods on both synthetic data and real-world applications.

Matrix Completion with Incomplete
Side Information via Orthogonal Complement Projection
Gengshuo Chang"
Wei Zhang
1
Lehan Zhang'
Abstract
focus on the low-rank properties of the matrix. Techniques such as nuclear norm minimization(Liang et al., 2022; Li et al., 2022; Yang et al., 2021) and alternating minimiza- tion(Jain et al., 2013; Gu et al., 2023) have been developed.
Matrix completion aims recover missing en- tries in data matrix using subset of observed entries. Previous studies show that side infor- mation can greatly improve completion accuracy. but most assume perfect side information, which is rarely available in practice, In this paper, we propose an orthogonal complement matrix com- plction (OCMC) model address the challenge of matrix completion with incomplete side infor- mation. The model leverages the orthogonal com- plement projection derived from the available side information, generalizing the traditional perfect side information matrix completion to the sce- narios with incomplete side information. More- over, using probably approximately correct (PAC) learning theory, we show that the sample complex- ity of OCMC model decreases quadratically with the completeness level. To efficiently solve the OCMC model, a linearized Lagrangian algorithm is developed with convergence guarantees. Ex- perimental results show that the proposed OCMC model outperforms sfate-of-the-ar methods on both synthetic data and real-world applications.
Apart from the low-rank property, studies show that if we have some prior information for the target matrix, i.e., side information, the accuracy can be improved furthermore. Typical forms of side information include knowledge about the column/row spaces (Herbster et al., 2020; Vlachos et al., 2018: 8: Zhang et al., 2019) and information represented by graphs (Elmahdy et al., 2022; Suh & Suh, 2022). For graph- based side information, recent works, such as community detection with stochastic block models (Zhang al., 2021) and hierarchical similarity graphs (Ahn et al., 2024) have established fundamental limits on sample complexity.
In this paper, we study the side information related to the col- umn and row spaces, which arise in many practical applica- tions. For example, in recommendation system, in addition to a small number of known ratings, we often have access to certain user and item features, which can help refine the rat- ings (Zhao & Guo, 2017: Han et al., 2019). Early research on side information focused on specific applications, such as collaborative filtering (Menon et al., 2011; Pan et al., 2010) and disease association prediction (Natarajan & Dhillon, 2014), integrating it with non-convex optimization methods. To systematically analyze the problem, researchers gener- ally assume that the side information is "perfect", meaning that the available side information can fully describe the row and column spaces of the desired matrix. Based this assumption, the problem has been analyzed from both the non-convex (Jain & Dhillon, 2013) and convex (Xu et al., 2013) perspectives, leading to the same conclusion that side information can greatly benefit completion accuracy.
1. Introduction
Low-rank matrix completion infers the entire data matrix from the partial known elements. This method plays a significant role in various fields, such as recommendation systems (Ramlatchan et al., 2018; Chen & Wang, 2022; Xu et al., 2021), multi-label learning (Xia et al., 2023; Liu al., 2023; Cabral et al., 2011), wireless channel estimation (Zhang et al., 2018; 2020), and image inpainting (Chen & Ng. 2022; Jia et al., 2022). Traditional matrix completion methods, known as transductive matrix completion, mainly
However, the perfect assumption is not always valid. In practice, the completeness of the side information can vary significantly (Chiang et al., 2015; Yang et al., 2020; Lu et al., 2016). This may undermine the effectiveness of methods relying on this assumption, making conclusions non-trivial. For example, in recommendation systems, we may lack complete knowledge of a user's preferences, which could help predict ratings. (Rafailidis Nanopoulos, 2015; Guo et al., 2019; Pujahari & Sisodia, 2019). Similarly, in multi-
Equal contribution 'Department of Information and Commu- nication Engineering, Harbin Institute of Technology, Shenzhen. Correspondence to: Wei Zhang <zhangwei.sze hit.edu.cn>>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
label learning, obtaining complete and precise item features is often challenging (Sun et al., 2021; Liu et al., 2021; Wei et al., 2019). Therefore, it is crucial to explore models that account for the potential incompleteness in side information.
OCMC model can be solved iteratively, significantly enhancing computational efficiency.
For synthetic data experiment, the proposed OCMC model achieves superior completion accuracy, especially in scenar- ios with highly incomplete side information. For real-world datasets, including movie recommendation and multi-label learning tasks, results show that OCMC consistently outper- forms state-of- methods, highlighting its potential for broader applications.
Unfortunately, research on incomplete scenarios remains rather limited. Existing research methods include enhancing the interpretability of models to achieve greater robustness (Lu al., 2016), which mainly address scenarios where the side information experiences small perturbations but do not directly discuss the model's behavior under incom- plete side information. Additionally, some methods address matrix completion by decomposing the target matrix into components and optimizing each component independently (Yang et al., 2020; Chiang et al., 2015). However, these approaches emphasize the properties of the matrix after var- ious decomposition, but ignore the low-rank property of the matrix as whole. A more detailed description of related work has been presented to Appendix A.
Notations: Given a vector / E R we denote its 2-norm by |41|. Given matrix H E Rm*x, we denote its (i,h)-th entry by Hej. || || || its Frobenius norm, ||]|| its nuclear norm and | ||2 for its 2-norm or operation norm. We denote the column space and row space of H by col(H) and row H), respectively.
2. Matrix Completion Model with Incomplete Side Information
Main contributions, The main contributions of the paper are summarized as follows:
2.1. From Complete to Incomplete Side Information
We propose an orthogonal complement matrix com- pletion(OCMC) model under the incomplete side in- formation, generalizing existing methods relying perfect side information to handle more general sce- narios. Specifically, after projecting the target matrix onto four orthogonal subspaces, we observe that the orthogonal complement projection plays a more criti- cal role in matrix completion. Based on these insights, the proposed OCMC model creatively utilizes the low- rank property of the orthogonal complement projection, which can effectively reduce sample complexity.
Let R E R be the rank-r desired matrix, where r << min n). N = max (m, (mx n). indicating that R is a typical
low-rank matrix. And Ω E {1, 2, ..... m] x {1, 2, .2....,,] n}
denotes the set of the indices of observed entries. We define the sampling operator Pn : Raxm 1R
{ Rij. (1,)) 0. (1,)) Φ
[Pa(R)];
In order to recover the matrix R from the sampling set 2 the nuelear norm is typically used as a convex relaxation of the rank function (Candes & Recht, 2012):
Based on the probably approximately correct (PAC) learning theory (Angluin, 1988), we derive that the sample complexity for OCMC model to achieve com- pletion error of is of the order:
|X||-
s.t. Px(X) Pn(R).
(I)
X
In this problem, all matrices satisfying the sampling con- ditions form feasible set. When the observed entries sufficient (Candes & Recht, 2012), the feasible set is rela- tively small, making it highly likely that the optimal solution corresponds to the desired matrix. However, as the num- ber of observations decreases, the feasible set grows, and the probability of the optimal solution being the desired matrix decreases. In the extreme case, when there is no observations, all matrices of the appropriate size are in the feasible set, and the unique minimizer is the zero matrix. The schematic diagram is shown in Figure 1.'
min (orp') log log
where P is linearly related to the incompleteness of the side information, and X' is a constant from the nuclear norm constraint. Thus, the sample complexity of proposed OCMC model decreases quadratically as the completeness level increases.
To solve the proposed OCMC model, we present an efficient linear ADMM algorithm that reformulates the original problem into multiple subproblems. This al- gorithm addresses the challenge of the OCMC model, which involves simultaneously optimizing the nuclear norm of the entire matrix and its orthogonal comple- ment projection. Unlike traditional ADMM methods, we approximate the subproblems by retaining only the second-order terms of the nonlinear component, enabling a closed-form solution. Consequently, the
Based on the above discussion, increasing the number of observations will reduce the size of the feasible set, while side information can further narrow without the need to increase the number of observed entries. For example, let matrices A E m and B E B represent the side
'The figure is generated via online plotting tool https:// www. www.chip www.phtppp..oooooooooooooooooooo onl in/..
2

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Without loss of generality, we assume the column spaces of A, B and A, B have overlapping, i.e., col(A) col( (A) = Ø, col(B) n col(B) = Ø. We also assume that A, B, A and B are semi-orthogonal matrices, i.e.
knal Yusditie
A A = I and similarly for the others.
obserratoon
Based on the definitions above, one has Á - [A, AJTA and B = [B, BB where TA and T3 refer to the transfer matrices. Then, the target matrix R can be expressed as
Maaris to comppleted
lowe rale
R A [A, MTT
[A, (
large foosibde
Dividing the matrix M' into four blocks gives
nactear norm intimater desttrdd
M
M 12
R [A, A
[]
M
M
Figure 1. Matrix completion under different sampling conditions.
= AM B +AM B AM AMM'B"+AN AA BT. (4)
information related to the column and row subspaces of R. respectively. In particular, when the side information is perfect, we have
To recover the target matrix R with incomplete information A and B, an intuitive approach is to impose the constraint from (4) on the problem in (1), similar to the formulation in (2). However, since A and B are unavailable, this approach is not valid. Nevertheless, the decomposition form of the target matrix in (4) remains important. Both transductive and inductive matrix completion can be derived from (4). If no side information is available (i.e., A = B Ø the first three terms vanish, and the fourth term becomes the entire matrix R. reducing the model to the transaction matrix completion. If perfect side information is available, then the last three terms vanish. Furthermore, existing models 22) for incomplete side information (Chiang et al., 2015; Yang et al., 2020) essentially separate the fully known part from the rest, i.e., the first term from the last three in (4).
col(R) [ CA)( row (R) S cB)
Thus, there is a projection representation relationship be- tween R and A, B, i.e., = AMB", where M can be referred to as the image matrix. other words, the tar- get matrix R fully lies in the spaces defined by A and B. Therefore, we can further reduce the feasible set in (1) by imposing the projection constraint, i.e., X = AMBT,
min X ||
s.t. (X) -P R), X AMB
Assuming A and B semi-orthogonal, we have |M||
||MB""] ||.. then (2) can be written as:
2.2. Orthogonal Complement Matrix Completion Model
min || s.t. Pa(AMB") = Po(R),
M
To utilize the decomposition in (4) and derive a valid model for matrix completion with incomplete information, define the following projection operations R + Rmxn; P (A PAB PA B()), and PA B ().
leading to the IMC formulation (Xu et al., 2013).
However, when side information is incomplete, the desired matrix can not be constrained to specific projection spaces, as the equality constraint in (2), i..., X AMB"T longer holds. For the purpose of analysis, we introduce the following notations. Let A E Rm and B E R"xrn denote the available (incomplete) side information, and À E RmXFA and B+ E gaxFu denote complete (perfect) side information. We further define Á E mRF and B e Raxia as the supplementary components associated with the perfect side information. For example,
(A = PAXPB,
PAB (X) PAX (X)(X),
P PA-B (X) XP2 PAB (X),
PA-B- = - -X PAX - XPB PAB((X,,
where A- E (m- and B E (n repre- sent the orthogonal complement matrix (Strang, 2000) of A and B which satisfies: rank( [A, A ' m, AT
col R)) C col( = col(AA U col(A)
0: rank( [B B) = n and B" B L = O. Additionally, PA = AAT mmmm and PB BBT E R= repre- sent the projection matrices related to A and B. For exam- plc, P (AB(X) refers to projecting X onto the interscction of column space of A and row space of B.
row R C col = col(B) U ()),
In this work, we define the completeness level of side infor- mation as
completeness level rank(A) (A) + rrankBB)
Brak(It) (R)
3

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Table I. The range of ranks for different matrix parts.
PART
MINIMUM RANK
MAXIMUM RANK
(A)(X)
min [rank( rank (B)) rank(A)
P PAB- (X)
P (X)
rank(B)
P PA-BL(X)
min rank A), rank(B))
P (A
+
PAB (x) + +PA +PAlB(X)
0
(A) + rank
is worth noting that target matrix R can be expressed as (5) Compared the expression in (4), the form in (5) only involves the incomplete side information A and B, which may enable the valid constraint for R. However, one can find that any matrix X E RR can be expressed as
R= PAB (R)++ R)--R)-PBBB PABP (R)
Nocter Norm
Rock
x=PAB X)
(6)
2 Complaanos Leadl of Informziian
therefore, directly imposing the constraint from (6) on the problem in (1) is not meaningful.
Compastenss Level Side Inforattion
(a) Rank comparison
(b) Nuclear norm comparison
Figure 2. We compare the runk and nuclear norm of A (R) and A B (X), where R is the desired matrix and X is a randomly generated matrix in R 100x 100 with the same rank as R.
To address this issue and derive a valid constraint on X from (6), it is necessary to analyze components (5) and ensure that the corresponding parts of X exhibit properties consistent with (5). Specifically, since the target matrix is low-rank, one can find that all four components in (5) must also be low-rank. Therefore, for the matrix completion task, the components of candidates X in (6) must maintain the low-rank properties to guide the recovery matrix towards the target R. In other words, this requires restricting the feasible set in (1) to the matrices whose components, as defined in (6), are low-rank. Moreover, enforcing the low-rank properties of each component in (6) enables more accurate estimation of target matrix R with fewer observations, as reduces the number of parameters to be learned. This advantage will be formally justified in Section 3.
complement projection P PA- B-B- (xX) is significantly greater than even the rest three parts combined. Thus, it is essential to restrict the solution such that P PA- A- A-B+ (X) has a low rank, consistent with the low-rant property of P (R).
Moreover, as shown in Figure 2, the completeness of the side information increases, P PA4 B- (R) and PA- B- (X) exhibit distinct trends. Specifically, both the rank and nu- clear norm of P PA B+ (R) show the approximately linear decreasing trend, where the rank curve of PA B (R) in Figure 2-(a) is straightforward. For the nuclear norm curve of P A- (R) in Figure 2-(b), since the projection is con- structed based on the subspaces of R itself, the decay ap- proximately at rate of 1/r. In contrast, for same-rank random matrix X, the rank of PA (X) remains nearly constant, and its nuclear norm decreases more slowly-at at a rate of approximately 1/n. This is because A and B are derived from the subspaces of the target matrix R, rather than from X itself. These empirical observations further highlight the distinctive low-rank property of P A B² (R).
In what follows, we will discuss how to impose the low- rank constraints for each part in (6). Interestingly, for any X E 1 one note that the first three parts in (6),
i.e, (X), PABL (X), and PA- ((X), inherently sat- isfy the low-rank property because they include at least one known side information matrix factor. However, the orthogonal complent A n (X) lacks any side informa- tion matrix factor, and its low-rank characteristics cannot be guaranteed for any matrix X. Therefore, intuitively, it is more important restrict the rank of the P B (X). To facilitate the discussion, we refer to P PAL B (-) as the orthogonal complement projection throughout this paper.
Based the discussions above, perform matrix com- pletion with incomplete information, we use the low-rank property of P PA- B- (X) as an additional constraint in (1) to further narrow the feasible set. Since it is not an equality constraint, we incorporate it into the objective function and consider solving the following problem:
Table illustrates the rank ranges of parts in (6) for an arbitrary matrix, highlighting that the special characteristic of R lies in the low-rank property of A B (R). It can be observed that, due rank(A) (A) S TA m and rank B) < TB & n, the maximum possible rank of the orthogonal
min X + A||P A B= (X)Il=
(n(X) (R).
(7)

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Part IV
Part
Part IV
Part II
Part IV
Part
Part IV
Galll
Part I
Part
Part III
Part
Ill
Part
Part III
Figure 3. The trend of components" variation as side information completeness varies. Parts I, HI II1, and IV correspond to the first four items (4). From left right, the images represent increasing levels side information completeness. The size of the shaded regions symbolizes the proportion of each component relative to the desired matrix.
The derived model in (7) is called the orthogonal comple- ment matrix completion (OCMC). In the objective of (7), |X|] and A B (X) ||. used to incorporate the low- rank property of X and P. AAABa B (X), accounting for both the global property and the property of orthogonal comple- ment. In addition, it is easy to verify that the problem in (7) is convex, ensuring that guaranteed to converge to a global optimum.
Pn(R) (7) by ((X,,, Riy):
min Σ E(Xi) + td (X)]l,,, (8) X (1.)e
where the function ((:-) -) is used to measure the differences at the observed positions. particular, for the squared loss, one has ((X,,. Ray) = (Xij Ruy)². Then problem (8) can be reformulated into the following soft constrained form:
Discussion about A: The parameters À in (7) is used to adjust the weight of [| (X)Il= based the com- pleteness of the side information. For example, when there is no side information, we have A = B = 0, then | ||... which indicates that no addi- tional effects can be achieved because no useful information included. This scenario can also be interpreted as setting + O, and the problem transforms into (1). As the side information becomes more complete, it can be learned from Figure 2 that there is a approximately linear reduction in || A- (R) therefore it is reasonable to set larger À in (7). By adjusting the values of X according to the com- pleteness of the side information, OCMC can effectively incorporate side information into matrix completion. Fig- 3 provides a visual representation of the aforementioned trends: the completeness of side information increases, the proportion of the orthogonal complement projection becomes smaller.
min Σ ((X;,, X
(iJ)R
s.t. || S and (A-n-(X)|l- P. (9)
IP A [R)
where A' and P are related to λr and A2 in (8). Similar to the role of in (7), the parameter P in (9) is also related to the completeness level of the side information. As completeness level inereases, we set smaller value for P. Here, for convenience, we define the feasible set of problem (9) x X X S X, ||P A- B- (X)Il+ S P).
To relate model (9) to the PAC learning framework, we define a function class FF based on the set X,
J = Xij X X).
(10)
Based on our definition, one can find there is a one-to-one correspondence between the function fx and the matrix X. Then, we can treat solving problem (9) as finding a function fx in the function class which minimizes the corresponded objective value in (9), i.e.
3. Recovery Analysis
min Σ {(fx(i. R.y). fx fXEF
(11)
In this section, we theoretically analyze the recovery accu- racy and sample complexity for the proposed OCMC model according to the PAC learning framework.
(K.j)en
Moreover, given arbitray X, we consider two types of emros: empirical error L(X) and generalization error L(X),
((X)
1
Σ ()x(
3.1. PAC Model
(i
PAC is theoretical framework that ensures, with enough samples, algorithm can produce model with small generalization error and high probability (Angluin, 1988). Using this framework, we will show the recovery error of the proposed OCMC model in (7) is bounded.
((X) ((..))p(((x((x.)).. R,;)],
where p denotes the sampling distribution over the observed entry positions in Ω. Thus, the empirical error calculates the average loss the observed positions, while the gener- alization error computes the expected loss over all entries. As we can see, the empirical error is relatively easy to cal- culate, but the generalization error is more important and
Considering the potential presence of Gaussian noise in observations, we relax the equality constraint (x(
5

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
more challenging to obtain. To evaluate the generalization error ((X) based on the empirical error ( we employ the PAC model (Angluin, 1988), leveraging the Rademacher complexity of function class F.
with probability least 1 8,
log(1/6)
((X) S f(x) + By
2|52|
Lemma 3.1. (Bartlett Mendelson, 2002) Suppose -(:--) a loss function with Lipschitz constant Le and bounded by B with respect to its first argument, and ō is a constant where
log 2N [22]
9C 9CL + n
+ 2 min 22L
[[2]
0 6 < 1. Let RF) be the Rademacher complexity of the Sunction class F (w.r.. Ω and associated with l):
where the related constants are defined in Lemma 3.2.²
Building on Theorem 3.3, the following lemma provides the sample complexity guarantee of our OCMC model.
[0
1
(F) =E, E.
sup XXISX EX
oal callXioto Riasa)
Corollary 3.4. For any > O, we define the e-error re- covery of R E(G [e(f(i,)) Riy)l S e. Then, when the number of observations is the order of
[22]
LIP
SP
where aa are random variables taking values of {+1} with equal probability. Then with probability at least - 8, for all f F, i.e., XX E X, the generalization error satisfies
min (P(211EM))
(22 log N
(P
(2NN
2
E²
log(1/0) 2|02
an e-error recovery can be achieved by solving (9).
((X)= S ((X + N (.(F) + B/
(12)
To further analyze the number of observations according to Corollary 3.4, we can adjust X and X2 to set the value of 22 BT I]. in (4). As shown P as || A B (R)ll. or A
From Lemma 3.1, since the last term in (12) is constant, the generalization error is influenced by the empirical error ((X) and the Rademacher complexity [R)[))(F)) By solving problem (9), the empirical error ((X) will be a small value. Thus, the most significant factor affecting the generalization error in (12) is the Rademacher complexity of F, which will be discussed in the next subsection.
in the Figure 2, the nuclear norm of the orthogonal comple- ment projection || AA (R)l, decreases approximately linearly with the level of completeness, suggesting that P follows an approximately linear trend. Consequently, based on the first term in Corollary 3.4, we can infer that as the completeness level increases, the sample complexity de- creases at approximately quadratic rate. This aligns with our intuitive understanding: the greater the completeness of the obtained side information, the more beneficial it is for our matrix completion task. More discussion about the number of observations are provided in Appendix D.
3.2. Main Results
In this part, we focus on analyzing the Rademacher com- plexity of F in (10), and establish the bound for ((X) by solving (9). Intuitively, as previously mentioned, the com- plexity of our function class should be closely related to the structure of the feasible set, i.e., to the parameters X' and P in Problem (9). Formally, Lemma 3.2 provides an upper bound on the Rademacher complexity.
4. Linear ADMM Algorithm
To solve the problem (7), we firstly introduce a variable Y as an auxiliary variable, then (7) is reformulated as follows:
Lemma 3.2. Let Q Rmxm be a matrix with columns Q -. and S E RRax be matrix with columns S = {s:}. which make [++I-PBBs hold for some μ >> O. Then, with the settings in (9). the upper-bound of Rademacher complexity function class F
min X.Y
|| + X|||I
QII+HI-PAl = I
s.t. (x PR) Y Y= -
(13)
The augmented Lagrangian function of (13) is given by
in (10), i.e. Ex)(Re(F),, is given by
8(X, Y, M, M2, B) | A||
log2N 2N
9CL,XB(Vm + vn) [
2L QSP
8 2 (P R 11 Y PPA-B (X)
3
[
where N = (max(mmne n) denotes the quantity representing
+ (o RR) + (M2, Y (X))) (14)
the size of the matrix, Q = max, ||q: ll2. S = max, || l12. Le and B are defined in Lemma 3.1, and C' is a constant. The detailed proof of Lemma 3.2 is provided in the Ap- pendix B. By combining Lemma 3.1 and Lemma 3.2, we can upper bound ((X) of the OCMC model as follows.
where M, are the Lagrangian multipliers, 8 is the penalty parameter. and (..-) denotes the matrix inner prod- uct: (A, B) = Tr(AB"). ). For simplicity, in this paper, we
*Our analysis makes no assumption on the sampling distribu- tion, making it more general than maffom--samlingg-bae.. results (Xu et al., 2013; Recht, 20. The connection between L( X and mean squared error is discussed Appendix C.
Theorem 3.3. For the problem (9), the generalization error ((X) can be upper-bounded by the following expression
6

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Ii.. while the algorithm can be extended to accommodate any loss function.
focus the squared loss ||
R= JK E R1000100 of rank 10. Side information ma- trices A and B are derived from the SVD of R = UEVT, where U, V E R 1000x10 and Σ E 100010 We then trans- form U and V by multiplying them with random matri- ces. Specifically, U is transformed as A = UT, where T E R0 with Ti ~ (O, 1), and B = VQ, following the similar transformation, where Q is a random matrix gen- erated similarly T. Making T and Q column full rank, the integer d is set d rx 17, where 1) is the completeness level. For example, with 50% completeness, v 50%, so d = 10 x 50% = 5. For simplicity, in our experiments, when we refer to the completeness of side information as 50%, it means that the completeness of both the row and column side information 50%.
Algorithm Linearized ADMM for OCMC with Squared Loss
1: Input: side information matrices A, B: sampled matrix (R):); maximum iterations K; parameters X, Po, Pmax. P.T
2: Output: X.Y.M,, M2
3: Initialize X = =Y = M = M = 0, h- =00 0
4: while k- < K do
5: Update X by solving (15)
6: Update Y k+1 by solving (16)
7: Update M by (17)
8: Update M. Mo+1 by (18)
9: Update gh+1 as: BB+1 min ( (mmxx: p
Three representative algorithms are selected as baselines: SVT(Cai et al., 2010), Maxide(Xu al., 2013), and Dirty- IMC(Chiang et al., 2015). We use the relative Frobe- nius norm difference as the performance metric: error R- R|] F R|] where R is the target matrix and i is the completed matrix. The sampling rate is defined as [2//m n, where Ω the set of the indices of observed entries, and m, n represent the target matrix dimension.
10: k = k +1
11:
end while
To solve the problem (14) iteratively, let & denote the iter- ation index. Given the current values X* Y M M the variables can be updated as follows:
x++1 = arg min 2(X,Y Y M .M
(15)
X
In Figure 4, we evaluate the completion accuracy of the pro- posed OCMC under different sampling rates. To ensure a comprehensive evaluation, we consider three levels of com- pleteness: low (1) = 20%), medium (1 = 50%). and high (1) = 80%). More experiments are provided in Appendix F.
rk+1= arg min 1(x*+1 k+1 Y, YMM,, 3),
(16)
M M + (P x+)= PR((R):;
(17)
M Mº + 3 k+1 -PA- (X x)).
(18)
the derivations of the closed solution of (15) to (18) and com- plexity analysis are provided in Appendix E. The workflow of our algorithm is summarized in Algorithm 1.
Results: From Figure 4, we can observe that our proposed OCMC consistently outperforms the established baselines across all three levels of completeness. With the exception of the Maxide, the completion accuracy of all matrix com- pletion models improves as the sampling rate increases. The completion accuracy of the Maxide remains at a relatively low level. We conjecture that it is because in incomplete situation, Maxide restricts the feasible set based on incorrect row and column information, excluding the true matrix from this feasible set. This situation further emphasizes the im- portance of methods for using incomplete side information. Among the remaining algorithms, SVT exhibits the lowest accuracy, because it does not use any side information.
This enhances computational efficiency for each subproblem can be solved iteratively and in parallel. Moreover, since the problem in (7) is convex, Algorithm 1 will converge to global optimal solution after a finite number of iterations (Yang & Yuan, 2013) and the convergence rate of linear ADMM is O(1/k) (Fang et al., 2015; Shi et al., 2015).
5. Experimental Results
In this section, we demonstrate the effectiveness of the proposed OCMC model and the linear ADMM algorithm through experiments conducted on both synthetic experi- ments and real-world applications. In the synthetic experi- ments, we primarily investigated the relationship between matrix completion accuracy and the number of observa- tions under varying completeness levels of side information. In the real-world application experiments, we focused on the multi-label learning (Goldberg et al., 2010) and movie recommendation (Harper & Konstan, 2015).
5.2. Multi-label Learning
In multi-labe, learning, each instance can belong to mul- tiple categories simultaneously. Since labels and features are often interrelated, and jointly low rank, matrix com- pletion methods have been introduced to capture the latent correlations (Goldberg et al., 2010).
We compared our proposed OCMC model with the SVT, Maxide, DirtyMM, as well as FPC (Ma et al., 201 la) and FNNM(Yang et al., 2020), which shows promising results in various practical scenarios. The dataset
Settings and Baseline:
5.1. Synthetic Data Experiments
Settings and Baseline: We set J, K E 100x 10 with ele-
ments Jıy, Kij ~ (O, 1), generating the low rank matrix
7

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
13-
120
17
-y- Bontox
SVT Beg OLMC
655
03
81
Sampling Rale
Sampling Rate
Sampling Rate
(a) Low completeness (20%)
(b) Medium completeness (50%)
(c) High completeness (80%)
Figure 4, Error VS. Sampling rate under different completion rate of side information.
Table 2. Comparison of algorithms on the "Arts" dataset with varying sampling rates
DATASET
w%
SVT
MAXIDE
DIRTYIMC
FPC
OCMC
FNNM
ARTS
10%
0.3500
0.5746
0.4591
0.3402
0.5249
0.5126
30%
0.4639
0.6435
0.6416
0.5012
0.7206
0.6825
50%
0.6053
0.6784
0.7648
0.6103
0.8358
0.7625
70%
0.7271
0.6991
0.8584
0.7592
0.9029
0.8326
90%
0.8695
0.7135
0.9266
0.8763
0.9596
0.9115
we selected is the web page classification from "Yahoo.com" (Ueda & Saito, 2002), which includes 1I distinct topics. For instance, in the "Art" category, there are 5,000 instances, each with 432 features and 21 label categories.
5.3. Movieleens-100k
In this experiment, we use the MovieLens-100k dataset (Harper & Konstan, 2015), which contains 100,000 ratings (ranging from to 5) from 943 users on 1,682 movies, and includes 23 user features (e.g., age, gender, occupation) and movie features (e.g., genre, release date).
We randomly pick 10% instances as the test set and use the rest 90% the training To conduct partial label assign- ment in the training set, for each label, randomly choose 10% positive and negative training instances and keep the remaining training instances unknown. The percentage of training instances w% ranges from 10% to 90% with an in- creasing step size of 20%. Notably, w% also represents the sampling rate. this experiment, we use Average Precision (AP) (Mazumder al., 2010) the evaluation metric.
Settings and Baseline: The data is divided into a training set and test set, with the proportion of the test set ranging from 0.1 to 0.9 in increments of 0.2. The performance of different methods is evaluated by the Root Mean Square Error (RMSE) on the test set, defined as:
RMSE
(Xi, R,,)² Σ (i)))ñ
Results: Table 2 summarizes the results for the "Arts" cat- egory. The best AP result is bold and second best result is underline. It can be learned that our OCMC achieves four best results and one second best result. These results demonstrate effectiveness the proposed OCMC model leveraging incomplete side information to improve perfor- mance in multi-label learning applications. Comparisons for other categories provided in Appendix F for reference.
where R,y is the sampled rating, Xij is the corresponding completed rating, and Q represents the indices in the test set. Like in multi-label learning, we choose SVT, Maxide, DirtyIMC, FPC and FNNC as baselines.
Results: The RMSE values for all methods at different sampling rates are shown in Table 3. The best AP result
Table 3. RMSE of algorithms on the "MovieLens 100K" dataset with the varying training set proportion.
PROPORTION
SVT
MAXIDE
DIRTYIMC
OCMC
FPC
FNNM
10%
2.3824
1,4512
1.3053
1.1503
1.8050
1.3533
30%
1.5523
1,4483
1.0251
0.9826
1.2249
1.0466
50%
1.3325
1,4415
0.9532
0.9013
1.0733
0.9701
70%
1.2284
1.4392
0.9321
0.8872
1.0033
0.9283
90%
1.1423
1.4336
0.8702
0.8625
0.9533
0.8983
8

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
bold and second best result is underline. As the pro- portion increases, the performance of most methods im- proves. Among them, DirtyIMC, FNNM and OCMC are applicable for matrix completion with incomplete side in- formation, demonstrating better completion performance compared to other methods. Notably, our proposed OCMC model achieves the best performance among all benchmarks, demonstrating its advantage effectively leveraging incom- plete side information for accurate recommendations.
Table 4. We compuate the residual norm: || P - R F and its normalized form: || A R
/|llll F of each dataset from
MovieLens- 100K and 11 datasets of "Yahoo.com".
CATEGORY
RESIDUAL NORM
NORMALIZED
MOVIELENS-10N
1122.5
0.9581
ARTS
71.2843
0.7882
BUSINESS
53.3929
0.5992
COMPUTERS
61.7102
0.7111
ENTERTAINMENT
60.3578
0.7162
EDUCATION
65.2612
0.7637
5.4. Discussion
HEALTH
60.2478
0.6609
RECREATION
64.6424
0.7663
The experimental results on real-world datasets, demon- strated in the previous subsections, show that OCMC effec- tively captures the characteristics of practical side informa- tion. This can be attributed to the fact that the proposed OCMC is designed for scenarios where side information is available but incomplete, which a common situation in real-workd applications. the following, we justify why side information often incomplete in practice, from both intuitive and geometrie perspectives.
REFERENCE
52.4684
0.6862
SCIENCE
65.0822
0.7642
SOCIAL
49.5415
0.6184
SOCIETY
69.95
0.7605
6. Conclusion
Intuitive and practical perspective: In recommendation systems such as MovieLens- 100k, side information typ- ically includes attributes of users (e.g., age, gender) and items (e.g., categories, genres). However, actual user preferences and item characteristics are influenced by additional latent factors that are not directly available but still affect the rating matrix. Thus, it unrealistic to assume that a few available features fully describe user behavior or item semantics. A similar situation occurs in multi-label learning, where side information such as feature descriptors or annotations only partially reflects the complex dependencies among labels.
In this paper, we investigated matrix completion problem with incomplete side information. A novel OCMC model is proposed that leverages the low-rank properties both the target matrix and its orthogonal complement projec- tion. Using the PAC framework, lish a generalization error bound for the OCMC model and show that the sample complexity decreases quadratically as the completeness level increases. Additionally, lin- ear ADMM algorithm is proposed to efficiently solve the OCMC model, which guaranteed converge to a global optimal solution. Experiments show that the OCMC model outperforms the existing matrix completion models in both synthetic and real-world applications, including multi-label learning and movie recommendation. As future work, we plan to integrate the proposed OCMC framework into neural network-based approaches to more effectively exploit side information and improve performance.
theoretically estab-
Subspace-based geometric perspective: If the side in- formation were complete, the column (or row) space of the target matrix would lie entirely within the subspace spanned by the given side information. However, this assumption does not hold in the datasets we studied. A formal check involves projecting the target matrix onto the side information subspace and evaluating whether the projection error is zero. Specifically, we can check whether the residual norm P. - R||F= = 0, where PA = A(A -)-1A7 AT. large residual norm indi- cates that the given side information does not fully span the target subspace. To illustrate this, the resid- ual norms the experimental datasets are shown in Table 4. As observed, these residual norms are large compared to the norms of the target matrix, confirming the incompleteness of the side information.
A Acknowledgements
This work was supported in part by the National Natural Science Foundation of China under Grant No. 62401 I 180, the Shenzhen Science and Technology R&D Funds under Grant No. GXWD20231 130104830003, the Guangdong Basic and Applied Basic Research Foundation under Grant No. 2025A1515011733
Impact Statement
These insights confirm that side information in real-world datasets is generally incomplete. This also helps explain the strong empirical performance of OCMC on benchmarks such recommendation systems and multi-label learning.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here.

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
References
Gu, Y., Song, Z.., Yin, J., and Zhang, L. Low rank matrix completion via robust alternating minimization in nearly linear time. arXiv preprint 2rXiv:230.11000 2023.
Ahn, J., Elmahdy, A., Mohajer, S., and Suh, C. On the fundamental limits of matrix completion: Leveraging hierarchical similarity graphs, 2024.
Guo, Q. Sun, Z., and Theng, Y.-L. Exploiting side infor- mation for recommendation. In Web Engineering: 19th International Conference, ICWE 2019, Daejeon, South Korea, June 11-14, 2019, Proceedings 19, pp. 569-573. Springer, 2019.
Angluin, D. Queries and concept learning. Machine learn- ing, 2:319-33 342, 1988.
Bartlett, P. L. and Mendelson, S. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-453 2002.
Han, J., Zheng, L., Xu, Y., Zhang, B., Zhuang, F., Philip, S. Y., and Zuo, W. Adaptive deep modeling of users and items using side information for recommendation. IEEE Transactions Neural Networks and Learning Systems, 31(3):337-74, 2019.
Cabral, R., Torre, F., Costeira, J. P., and Bernardino, A. Matrix completion for multi-label image classification. Advances in Neural Information Processing Systems, 24, 2011.
Harper, F. M. and Konstan, J. A. The movielens datasets:
History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
Cai, J.-F., Candès, E. J., and Shen, Z. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4):1956-1)))
2010.
Herbster, M., Pasteris, S., and Tse, L. Online matrix com- pletion with side information. Advances in Neural Infor- mation Processing Systems, 15:20402--24444 2020.
Candes, E. and Recht, B. Exact matrix completion via convex optimization. Communications of the ACM, 55 (6):111-119, 2012.
Jain, P. and Dhillon, S. Provable inductive matrix comple- tion. arXiv preprint arXiv: 1306v 3326.0626, 2013.
Chen, J. and Ng, M. K. Color image inpainting via robust pure quaternion matrix completion: Error bound and weighted loss. SIAM Journal on Imaging Sciences, 15(3): 1469-1498, 2022.
Jain, P., Netrapalli, P., and Sanghavi. Low-rank matrix completion using alternating minimization. In Proceed- ings of the forty-fifth annual ACM symposium on Theory of computing, pp.
2013.
Chen, Z. and Wang, S. A review matrix completion for recommender systems. Knowledge and Information Systems, 64(1):1-34, 2022.
Jia, Z., Jin, Q., Ng, M. K., and Zhao, X.-L. Non-local robust quaternion matrix completion for large-scale color image and video inpainting. IEEE Transactions on Image Processing, 31:3868-3883 2022.
Chiang, K.-Y. Y., Hsieh, C.-J., and Dhillon, I. S. Matrix com- pletion with noisy side information. Advances in Neural Information Processing Systems, 28, 2015.
Kakade, S. M., Sridharan, K., and Tewari, A. On the com- plexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances Neural Information Pro- cessing Systems, 21, 2008
Elmahdy, A., Ahn, J., Mohajer, S., and Suh, C. The optimal sample complexity of matrix completion with hierarchical similarity graphs. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 2409-2414, 2022.
Koren, Y. The bellkor solution to the netflix grand prize. Netflix Prize Documentation, 8 81(2009):1-10, 2009.
Fang, X., He, B., Liu, H., and Yuan, X. Generalized alter- nating direction method of multipliers: New theoretical insights and applications. Mathematical Programming Computation, 7(2):149-188) 1000-187111111 2015.
Li, X., Zhang, H., and Zhang, Matrix completion via non-convex relaxation and adaptive correlation learning. IEEE Transactions on Pattern Analysis and Machine In- telligence,
2022.
Goldberg, A., Recht, B., Xu, J., Nowak, R., and Zhu, Transduction with matrix completion: Three birds with one stone. Advances in Neural Information Processing Systems, 23, 2010.
Liang, H., Kang, L., and Huang, J. A robust low-rank matrix completion based on truncated nuclear norm and Lp-norm. The Journal of Supercomputing, 78(11):12950- 12972, 2022.
Gu, S., Xie, Q., Meng, D., Zuo, W., Feng, X., and Zhang, L. Weighted nuclear norm minimization and its applications to low level vision. International journal of computer vision, 121:183 208, 2017.
Liu, C., Wen, J., Luo, X., and Xu, Y. Incomplete multi- view multi-label learning via label-guided masked view- and category- aware transformers. In Proceedings of the
10

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
AAAI Conference on Artificial Intelligence, volume 37, pp. 8816-8824, 2023.
Raghunandan H. Keshavan, Andrea Montanari, S. O. Matrix completion from few entries. IEEE Transactions on Information Theory, 5666):2980-2998, 2010.
Liu, W. Wang. H., Shen, X., and Tsang, W. The emerging trends of multi-label learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(11):7955- 7974, 2021.
Ramlatchan, A., Yang, M., Liu, Q. Li, M., Wang, J., and Li, Y. A survey of matrix completion methods for recom- mendation systems. Big Data Mining and Analytics, 14):: 308-323, 2018.
Lu, J., Liang, G., Sun, J., and Bi, J. A sparse interactive model for matrix completion with side information. Ad- vances in Neural Information Processing Systems, 29, 2016.
Recht, B. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(12), 2011.
Shamir, O. and Shalev-Shwartz, S. Matrix completion with the trace norm: Learning, bounding, and transducing. The Journal of Machine Learning Research, 15(1):3401-
Ma, S., Goldfarb, D., and Chen, L. Fixed point and Bregman iterative methods for matrix rank minimization. Mathe- matical Programming, 128( (3:3133333353 2011a.
3423, 2014.
Shi, W., Ling, Q., Wu, G., and Yin, W. A proximal gradi- ent algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing, 63(22):6013- 6023, 2015.
Ma, S., Goldfarb, D., and Chen, L. Fixed point and bregman iterative methods for matrix rank minimization. Mathe- matical Programming. (111)3311333)) 1b.
Strang, G. Linear algebra and its applications, 2000.
Mazumder, R., Hastie, T., and Tibshirani, R. Spectral reg- ularization algorithms for learning large incomplete ma- trices. The Journal of Machine Learning Research, 11: 23222, 2010.
Suh, G. and Suh, C. Graph-assisted matrix completion in multi-clustered graph model. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 3156-3161, 2022.
Menon, A. K., Chitrapura, K.-P., Garg, S., Agarwal, D., and Kota, N. Response prediction using collaborative filtering with hierarchies and side-information. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 141-149, 2011.
Sun, L., Feng, S., Lyu, G., Zhang, H., and Dai, G. Partial multi-label learning with noisy side information. Knowl- edge and Information Systems, 63:541-564, 2021.
Töscher, A., Jahrer, M., and Bell, M. The bigchaos solution to the netflix grand prize. Netflix Prize Documen- tation, pp. 1-52, 2009.
Natarajan, N. and Dhillon, S. Inductive matrix completion for predicting gene cene-disease associations. Bioinformatics, 30(12):i60-i68 2014.
Ueda, N. and Saito, K. Parametric mixture models for multi- labeled text. Advances in Neural Information Processing Systems, 15, 2002.
Nie, F., Huang, H., and Ding, C. Low-rank matrix recovery via efficient schatten p-norm minimization. Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 655-661, 2012.
Vlachos, E., Alexandropoulos, G. C., and Thompson, J. Massive mimo channel estimation for millimeter wave systems via matrix completion. IEEE Signal Processing Letters, 25(1 1):1675-1169, 2018.
Pan, W. Xiang, E., Liu, N., and Yang, Q. Transfer learn- ing in collaborative filtering for sparsity reduction. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 24, pp. 230-235, 2010.
Wei, Y., Gong, C., Chen, S., Liu, T., Yang, J., and Tao, Harnessing side information for classification under label noise. IEEE Transactions on Neural Networks and Learning Systems, (1(9):317833199 2019.
Pujahari, A. and Sisodia, D. S. Modeling side information in preference relation-based restricted boltzmann machine for recommender systems. Information Sciences, 490: 126-145, 2019.
Xia, Y., Tang, M., and Wang. P. Bi-directional matrix com- pletion for highly incomplete multi-label learning via co-embedding predictive side information. Applied Intel- ligence, 53(23):28074-2809 2023.
Rafailidis, D. and Nanopoulos, A. Modeling users' pref- erence dynamics and side information in recommender systems. IEEE Transactions on Systems, Man, and Cy- bernetics: Systems, 46(6))782-792, 2015.
Xiong, W. Cheng, G., Schindelhauer, C., and So, H. C. Robust matrix completion for elliptic positioning in the presence of outliers and missing data. IEEE Transactions on Geoscience and Remote Sensing, 61:1-12, 2023.

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Xu, K., Zhang, Y., Dong, Z., Li, Z., and Fang. B. Hybrid matrix completion model for improved images recovery and recommendation systems. IEEE Access, 9; - 149359, 2021.
Xu, M., Jin, R., and Zhou, Z.-H. Speedup matrix completion with side information: Application to multi-label learning- Advances in Neural Information Processing Systems, 26, 2013.
Yang, and Yuan, X. Linearized augmented lagrangian and alternating direction methods for nuclear norm minimiza- tion. Mathematics of Computation, 82(281):301-329, 2013.
Yang, L., Kou. K. I., and Miao, Weighted truncated nu- clear norm regularization for low-rank quaternion matrix completion. Journal Visual Communication and Image Representation, 81:103335, 2021
Yang. M., Li, Y., and Wang, Feature and nuclear norm minimization for matrix completion. IEEE Transactions Knowledge and Data Engineering, 34(5)21100-219,, 2020.
Zhang, Q., Tan, F., and Suh, Community detection and matrix completion with social and item similarity graphs, 2021.
Zhang, W., Kim, T., Love, D. J., and Perrins, E. Leverag- ing the restricted isometry property: Improved low-rank subspace decomposition for hybrid millimeter-wan wave sys- tems. IEEE Transactions on Communications, 66(11):
5814-5827, 2018.
Zhang, W., Kim, T., Xiong, G., and Leung, S.-H. Leveraging subspace information for low-rank matrix reconstruction. Signal Processing, 163:123-1331 13,, 2019. ISSN 0165-1684
Zhang, W., Kim, T., and Leung, S.-H. A sequential subspace method for millimeter wave MIMO channel estimation. IEEE Transactions on Vehicular Technology, 69(5:3335 5368, 2020.
Zhao, F. and Guo, Y. Learning discriminative recommen- dation systems with side information. In IJCAI, volume 2017, pp. 3469-3475, 2017.
Zhou, C., Gu, Y.. Shi, Z. and Haardt, M. Structured Nyquist correlation reconstruction for DOA estimation with sparse arrays. IEEE Transactions on Signal Process- ing, 11:1849-1862, 2023.
12

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Here, present a detailed description of related work in Appendix A. Detailed proofs of Lemma 3.2 and Corollary 3.4 provided in Appendix B and Appendix D respectively, which are the most erucial parts of our theory. Appendix E provides detailed derivation of Algorithm 1. More experiments are presented in Appendix F and the full table of multilabel leamnngg outcome is also in the Appendix F.
A. Related Work
Transductive Matrix Completion: In most cases, matrix completion refers to transductive matrix completion. This approach focuses on completing low-rank matrix using limited number of sampled entries, relying only on the low-rank property of the matrix. Early studies on matrix completion were developed for applications like collaborative filtering, such as the famous Netflix Prize (Koren, 2009; Töscher et al., 2009). Several theoretical foundations have been established in this field.
One remarkable milestone was established in (Candes & Recht, 2012; Recht, 2011)., which demonstrated that, the entries of the desired matrix are uniformly sampled, solving the nuclear norm model
min
X|I s.t. ( Pn
allows to perfectly complete low-rank matrix X E R from ON log" N) samples, where N max (m, n). (Recht, 2011) 1) demonstrates the theory from the perspective of sampling with replacement, arriving at the same sample complexity results. Based on these basis, series of convex relaxation algorithms have been developed. As mentioned above, (Candes & Recht, 2012) proposed a nuclear norm relaxation framework, while (Cai et al., 2010) introduced the singular value thresholding approach. By calculating the following iteration, SVT combines nuclear norm relaxation with proximal gradient methods:
Xx = DD(Kki
Y = Y 6.Pa -R--Xo Xx)).
Some studies also employ variants of the nuclear norm to approximate the rank of a matrix, such as (Gu et al., 2017; Nie ct al., 2012).
Another popular approach is by matrix factorization, which has become a widely applicable and empirically successful method for low-rank matrix completion. In this kind of approaches, the low-rank target matrix represented in bilinear form:
X = UVT
where U E RMXp,, V E TRRPP. By constraining the dimensions of the factor matrices, i.e., the size of p. we can effectively limit the rank of the target matrix based on the principles of matrix multiplication.
The most known algorithm through matrix factorization is the alternating minimization (Jain al., 2013), which formed a major component of the winning entry in the Netflix Challenge. This algorithm performs matrix completion by solving the following problem:
(P - Psp (R) min
[| P mill gR [Pa((U*TT) (A(
min
UERmxP, VeREXP
Although the overall problem is non-convex, each sub-problem is typically convex and can be solved efficiently. (Jain et al., 2013) provided convergence guarantees for alternating minimization in matrix completion. In addition, several gradient-based algorithms have proven effective. For instance, (Raghunandan H. Keshavan, 2010) proposed the Spectral Matrix Completion method, considering a variant of matrix completion.
Inductive Matrix Completion: Inductive matrix completion leverages side information about the row and column spaces of the matrix to improve the accuracy of the completion process. Various algorithms have been applied across domains like collaborative filtering response prediction, and gene-disease association prediction, significantly enhancing efficiency. Most of these algorithms rely on various matrix factorization techniques.
For example, studies by (Jain & Dhillon, 2013), as well as (Xu et al., 2013), focused on matrix factorization for the matrix
13

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
completion problem with side information. Both approaches utilize representation trick:
R = AMB"
where R is the desired matrix, and A and B are side information matrices corresponding to the row and column spaces, respectively. Their results suggest that, by optimizing min || s.t. Pa(AMB) = P
M
where the sample complexity can be reduced to NloogN).
Considering the latent noise in side information, a more recent study (Chiang et al., 2015) generalized this model by introducing a dirty statistic model, given by:
X = AMB +N.
Then, they optimize the following problem: | + + ||
min
s.t. Pa(AMB" + = (R)
M.N
This work proposes method for evaluating the quality of side information and demonstrates that sample complexity be reduced even with noisy side information, depending its quality.
Additionally, (Lu et al., 2016) focused on the embedded matrix M and proposed a sparse interaction model:
min M.E.
IXMYT E| + AM M||
Ag El| subject to Po E) (n(R).
which achieves similar results on the effectiveness of imperfect side information in matrix completion.
B. Proof of Lemma 3.2
Proof. We separately prove that the Rademacher complexity is less than each term on the right side in Lemma 3.2. Specifically, we will show that
log 2N
Re(F) < 2SP
(19)
[S
9C 9CL2X Vm + VT)
R₂(F)
(20)
[
To prove the first inequality in (19), we mainly the following lemma.
Lemma B.1. (Kakade al., 2008) Let S₂ (W Raxn | W}. A (1,
||A A gax we
have
log 2n
E
sup WES,
Σ trace W W.,)
S 22WWV
m71
This Lemma is corollary of Theorem 1 in (Kakade et al., 2008).
Recalling the definition of the Rademacher complexity, the Rademacher complexity of F is given by
RFFF) E
sup
aa a (XinJa Rimia)
(21)
[2
|X|||
LI|P A-m- SP
SP
Using the contraction principle of Rademacher complexity(see (Bartlett & Mendelson, 2002)), the expression in (21) bounded by
Ω
L Ω
R. (F) & E,
sup
0 XiaJa
(22)
||||| EX
a=1
||| P---BB
(X)ISS
14

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
We define the matrix I as follows:
Ja. if = la and j Ja
0.
otherwise.
Then, by representing the inner product matrices, we can rewrite (22) as follows:
Le (T, x)
Le tr tr(x*r)
Re(F) s E.
sup ||||| SX |IP (XIII
1B
sup ||X SX
(23)
[22
[| L I)ISSP
To proceed with (23), we let Q E IR mm be a matrix with columns Q = }.9:}. and let E R"x" be a matrix with columns
S = { where (I μI PB S I = Q + pT PA) for some μ > 0. Then, we have
tr tr(x"1)
Q + pI PI - ,l PB)ST"
Then, by substituting II in (23), we have the following inequality:
LE tr pu PA)X(I+ + - PP))ST 12
Rx) S E.
sup JX Sx
(24)
AP SP
To apply the Lemma B.1 for (24), we consider the following definition.
Definition B.2 (μ-relaxation for operation PA- B (-)). For any matrix E mx and p we define the linear
operation PM B (+) as the p-relaxation for A B (-):
pk BLB
B (R) (I μI PA)R(( pl p
The operation PAI B (+) can be viewed 1 PM Ba ()). Here, μ is called the relaxation factor.
The advantage of Definition B.2 that allows the projection operation to become an invertible operation while maintaining the constraints some extent, as μ can be arbitrarily small. This facilitates analysis and the generalization of the results. that when μ very small, the constraint on ||P A- (X)Il+ should yield
Based Definition B.2, result very close to | n (X)lI. The simulation results in Figure 5 are also consistent with this observation. Thus, we
intuitively
can approximate the constraint |P A- B- (X) ||+ S P by PM A
(X [X)|= S P in (24).
Nclear Norm Ratio
2.00
5.05
6e
9.95
Completion Level of Side Information
Figure 5. Nuclear norm ratio [PPA B (X) - B (X) for (0,2x 10-3 -0=3,xx 10-3,0000000 6 10-3 and completeness levels (0.1.-.. ,11, where X a randomly generated 100 100 matrix. The experiments were repeated ten times, and the average results
are shown. The maximum difference in nuclear norms, the same completeness level, is less than 1.5% across different values of
15

---

Matrix Complction with Incomplete Side Information via Orthogonal Complement Projection
Therefore, express (24) follows
!
L
R(F S E,
sup 1XII-X
a QQ + - P PB)S] linio
|| A-mn SP
L
E
sup
Ja
9i
T (I μI PA) μI -BB)s3a
|X||
Q=1
||P A- p SP
!
L
E,
sup
tr [TT uI PA)X(I + pI PB)sjagi Vial
!
|X|] SX ||Pa A L. (X)II.
a=1
[ [PAt
L
E
tr
A-B' BB (X)8ja Haa
(25)
|X||SXX
[22
| A m.
(X) SP
where the final equality uses the definition of P
in Definition B.2.
then the expression in (25) can be further bounded by Using Lemma B.I, we let Q max; |1 S = max, ||8 l,
L !
log 2N
Re(FF (F) S Eg
sup X
oa tr [PM (X
(26)
SX
[|P A- 1 (X) SPP
which concludes the proof of the first lower bound (19) in Lemma 3.2.
For the second lower bound (20), using the same trick in (Lu et al., 2016), we can divide the sampling matrix I into two parts based on "hit-time." Specifically, by setting a threshold f, any entry F exceeding t indicates a frequently sampled element, while values below suggest infrequent samples. Using this criterion, we obtain matrices and F follows:
Tijs Di 2
T sj Pij
Eaj
0, otherwise
0. otherwise.
Thus, we have r E F. and the Rademacher complexity in (23) can be bounded follows:
sup 1
R²(F) Ey
Pi ((Xij, Ris)
|X|I SX
O
LIIP A (X)
=E,
sup
Σ
Eig E(Xij, Rey)
+ E
sup
Σ
Fis
(Xig,
Rij)
(27)
[ SX [X)II.SP
|X
SX
i.
SP
|PAI Ral (X
According to the Definition B.2, we have E(Xig, Riaia) S B, then the first term in (27) be bounded follows:
1
B
E
sup
Eigl(Xig, Rimia)
S E.
sup
Eij
X
I
SX
Ω
1j
XXI|
SX
Ω
(X)
SP
||
(X)II. SP
B
< E,
sup
E
(28)
|X||<XX
[X]]
16

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
For the second term in (27), using the Rademacher contraction principle, we bound by:
Le
F,
sup SX [X
r Pi
E
sup X SX n SXP
(T, F)
(29)
I|P
SP
LIPT
Using Hölder's incquality, the right-hand side (R.H.S.) ..S.S.)... of (29) can be bounded by
LE FT,F)
LE [2
E,
sup X SI A- SP
E
sup XXII
(30)
LIP A B (XII.SP
According to (28) and (30), the Rademacher complexity can be bounded as follows:
L S2
R (F) & Egg
sup ||X|| SX LIP JlPAinn PXP SP
E
R,
sup XX (X)
(31)
122
SX
LIP
Based on Lemma 10 and Lemma 11 in (Shamir & Shalev-Shwarte 2014) and Definition B.2, the expression in (31) can be further bounded by:
B
(CL.VIl/m+Vi
RxFF) < Vt +
(32)
1/2
Then, we set t as the optimal minimizer for the R.H.S. of (32), i.e., t ACI.ev((Vm++ we get
11
9C4AB(( nT)
En (F]]
(33)
|22|
In summary, after combining (26) and (33), we have
log 2.N
9CI,XB(VmI + Vn)
En (F)) < min
2LOSSP
[22
[22
which concludes the proof of Lemma 3.2.
C. Extending the Generalization Bound to MSE
The generalization error bound established in Theorem 3.3 is independent of the sampling distribution. In this part, we show how this distribution-fii bound can be extended to the mean squared error (MSE), which is widely used in matrix completion.
In Theorem 3.3, provide generalization error bound that holds under any sampling distributions. It is important to note that the definition of the generalization етrо ((X) depends on the given sampling distribution, i.c..
((X) ((s))>> [e(Xij, Raj)]-
In particular, for squared loss under uniform sampling, [(X) corresponds to the MSE:
MSE(X) E(. [(X,, R
To clarify the connection between the bound of L(X) in Theorem 3.3 and MSE key evaluation metric in matrix completion-wwe we have the following analysis. Under the squared loss, one can find that the difference between L(X) and MSE is that L(X) is expectation under an arbitrary sampling distribution while MSE assumes the uniform distribution U. From Theorem 3.3, we denote the bound of ((X) as W, then
((X) = E(s.i> [(X.j - R, < W.
Applying the total variation distance bound on expectation for discrete distributions, we obtain:
Búi)~ [(x.j R < E(ts)>> [X,, R, 2M (V, W + 2MM TV W
where M is the upper bound of (X,z 3, and TV (U' represents the total variation distance between the uniform and arbitrary sampling distributions. This result extends our bound to MSE under arbitrary sampling distributions.
17

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
D. Discussion about the Number of Observations
We first provide detailed derivation of Corollary 3.4. Recalling the Theorem 3.3, we have
1og(1/5)
log 2N
9CL m + vn)
( - ((x) + BV 2/
+ 22mi 2LPOSP
|22|
Considering the e-error recovery, i.e.
((X) = B(i [C([(,,)) Raj)D Se
for any e >> 0, then we let
log(1/6) ((x) - ((x) + +B/
log 2N
9C DCLeXB(Vm + vn) SC.
+ 2 min
2LP
(34)
2|01
[
[0]
As discussed in Section 3, the empirical error is a relatively colt-controlled quantity. Therefore, we do not consider the impact of this term here, Then (34) can be expressed follows:
log(1/5)
log 2N [
9CL2X Vm VT)
B
+ 2 min
2SP
Sc.
(35)
2/0]
[2
After separating the term Ω in (35), we have
log(1/5)
log 2N e2
9CL m + vn)
BV
+ min 2LP
(36)
2e
22
We handle the two terms in the minimum of (36) separately, As example, we only consider the first term. For the second term,the approach is the same as the first term. Specifically, we have the following
(/)( + 2SL
log 2N
BV 2ea
S S/..
Taking the square of both sides of the above expressing gives
2
log(1/))
log 2N + 4LOOSP
B
$ |12..
(37)
2²
22
Then, expanding the square operation in (37) yields
2 (1/)
log(1/8) 2ea
log 2N 2N
log 2N
+ 2B 4L QSP
+ 12
S [2].
(38)
22
e²
2²
By ignoring the constant terms in (38) that are independent of the matrix size and lower-order terms, we can derive the following conclusion for the number of observations:
|o| = O (P*logN).
(39)
Similarly, by handling the second term in (36), we obtain the following:
x2 X2VN
| = o
(40)
2
Combining (39) and (40), we draw the conclusion in Corollary 3.4:
Ω = min (o p2 2o'log
(0(2"1
log N
x2 V 2
We provide detailed discussion of Corollary 3.4 under different side-information scenarios. For simplicity in our analysis, we focus one of the two lower bounds, as this is sufficient to demonstrate the effectiveness of our model.
When the side information is perfect, we focus on the first lower bound. P remains invariant with matrix dimension N, then the sample complexity required is Ollog N). This result is consistent with the result of (Xu et al., 2013), where it is proved that Ollog .N observations are required for the matrix completion task by solving IMC. However, in (Xu et al., 2013), it is assumed that the observed positions are uniformly distributed, which facilitates the analysis using convex optimization techniques. In our proof, we leverage theories from PAC learning, thereby avoiding any assumptions regarding the distribution of the observed positions.
18

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
When we have incomplete side-inforration, we focus the first lower bound. The sample complexity required is O(p2 N), where P decreases the completeness increases. Moreover the sample complexity decreases quadratically with the value of
When we have no side information, we focus on the second lower bound. We get X = O(VN) as reasonable assumption (Shamir & Shalev-Shwartz, 2014), then the entire sample complexity is O(N2/S), which is consistent with the conclusion of standard matrix completion without any assumption of sampling distribution (Shamir & Shalev-Shwartz, 2014).
is evident that our conclusions apply to the more general matrix completion problems existing in the literature, for the reason that our model differs from traditional decomposition-be based models (Yang et al., 2020; Chiang al., 2015). We focus not only the components after decomposition but also the overall low-rank property of the matrix.
E. The details of Algorithm!
The Detailed Derivation of Closed-Foo Fooee--Frmmmo Solutions: In this section, we provide a detailed derivation of the closed-form
solutions for Algorithm 1. Recalling (14) in Section 4
Y 11 + 8 |Pa(X) - Pn(R)] + B Y P
2(x, Y. M1, M2. B) -I =| X Il. + X
2
2
+ (M, (x) (n)(R) (M2, Y PA B (X)),
then we solve X in (15) and Y in (16) separately.
Update X:
k++1 arg min e(X, Y M M B)
X
3
P Pn((X) - Pa(R) + 2 1|Y - PP (X) + (MF.
=arg min
|
|- +
X
2
2
Po(X) Po((R) + (M - P
Adding constant terms
|M P. and
1 |M |3: and completing the square, we have:
23
23
x k+1
arg min
X |- + 2
PP (X) - Pr. (n((R) (MK,Pa(X Pr(X) - PR)(R) + M
X
23
8 Y
1
P P (x) + +(M Y - PALL (X))
2
2/3
8 2 P R) +
M B + 2 PP (X) y
3
M 11
mig | |
(41)
The presence of both nuclear norm terms and quadratic terms in the objective function complicates the overall problem, making it challenging to achieve convergence through iterative methods. However, in practical implementations, we often do not require each iterative step be solved high precision for the algorithm remain viable. Building on this principle, propose approximating the subproblems by linearizing the quadratic terms of the objective function.
Specifically, we use the following approximate strategy to handle [PPo(X - R) + Mf 11 and (X) Y - 1|:::
M
)(X) = f(x*) (g* X x 1
x 1
where f is differentiable at X g is the gradient at X and 0 is the proximal parameter.
Applying the approximate strategy for the second and third parts of (41), we have:
R
h
M
M
[P - R) +
RJ
R)
+
+2 < Px -R+
)
X - x*
+ - -x113
B
B
3
M
M
M
(P)
x +
112 ~ |P |PA-B4 (x (
Y² +
1 +2 < P (x* y +
B ) - x
+ + - 1
19

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Substituting the results back to (41), we obtain:
B 2
M
M
x arr min
X
||aa(X*
R)
1 B++B<Pa(X*
R+
8 )
X
X
X
x
25
M
YY* M
8
+ /
P Y
F + 3 <
PA
x X
X
x
25
M
M
3
arg min X + B Pn R
(X* -
x
x*
>
+ +
X
x
11
3
B
7
By adding constant and completing square, we have:
x se arg min || . + -| x x I 2
Pa(x
-R+
MI,
+ T
PA -Yx
-
M
"B - )
X
B
arg min
X 233
X
ト || x Pa( R+
M
3
)
2
PA
T
B (X*-X*
M
)1
B )|
(42)
To solve this problem in (42), we utilize the following lemma.
Lemma E.1. (Cai et al., 2010: Ma et al., 2011b) Given M Rmxx and d > let M UEVT be the SVD of M and I be the identity matrix. We define the following "singular value shrinkage" operator:
Ss == U(E -5r)+ b1)+v²
where (a)+ = max(a, 03. Then, it can be shown that
(M(M) arg min 8 N||
- II M
Applying Lemma E. to (42), have the closed form solution for updating X X
x k+1 -.
x*
T PP
-RR
M
I
A- - -x + Mr
3 }
2
B
2
For the update of Y.
yk+ = arg minnA|yii + (M, PA'B (x - Y) IP 1 -
Y
Adding constant terms and completing square, we have
X
M 1
y arg min Y B
Y
+ 11 P (X*+1)
The update for + is considerably simpler than that for x++11 and thus we do not require linearization. By applying Lemma 1. we have
(PALBI M
k+1 y =S3
For the regularization parameter 3, we adopt an incremental strategy to accelerate algorithm convergence. Specifically, we define a growth factor p and an upper limit 8max. During each iteration, ,3 is updated as p 8 until 3 reaches 3max at which point the growth stops. The updates of M, and M2 follow the standard update rules in the ADMM algorithm.
In summary, we have:
x+1 =S.
x
T P 2
R+
M
T PA-B-(X' (X -xx
yh +
Ma M
B
2
B
M
x++1 S3 PA-BI(XK+) x-t
8
M k+1 x
M + 8 (Pr (x-+ x+11 PP)()) (R)),
M M M2 + 8h kt1 P PA-B- X *+))),
gh++1 mmin33ma p.3*).
Therefore, we have completed the detailed form of Algorithm 1.
Computational Complexity Algorithm For target matrix E RRmx and side information A Raxdd
B E Ruxd
20

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
(for convenience, here we assume r'A" = =rB = =d), the per-iteration complexity of the linear-ADMM algorithm for OCMC consists of three parts:
Calculating PA+ B4 (X): O(min(dmm dmm,, dmn + dn²))
Singular value shrinkage: (mmin(mmn,,nmm
Matrix inner product: ((m)).
The total complexity is dominated by the full SVD in singular value shrinkage step, i..., (mmmmm',,mmmm For large-scale problems, we can replace the full SVD with more efficient methods, such as randomized SVD and Lanczos method, whose complexities are Omm + r'mm m + r²) and (rmm)), respectively, where r is rank of R.
F. More Experiments
To further validate the effectiveness, robustness, and generalizability of the proposed OCMC model, we present several additional experiments in this appendix. These include analyses of the relationship between completion accuracy and the completeness of side information, the sampling rate required to achieve high-accuracy completion, the impact of noisy side information on performance, the comparison between OCMC and DirtyIMC under fully complete side information, and a comprehensive evaluation on multi-label learning datasets. All synthetic data are generated following the setup described in Section 5 of the main text, and all reported results are averaged over 10 independent runs to ensure statistical reliability.
Additional Results for Figure 2: To further support the observations in Figure 2, we conduct additional experiments using matrices with different ranks. The nuclear norms of P A B= (R) and P A- B (X) are summarized in Table 5.
Table 5. Nuclear of orthogonal complement under different completeness levels of side information.
Completeness level
0.2
0.4
0.6
0.8
1
r 5
Target matrix
1
0.66 0.05
0.40 + 0.03
0.22 = 0.03
0.08 = 0.01
0 + 0 0.94 + 0.01
Random matrix
1 + 0
0.99 + 0.004
0.98 + 0.007
0.97 + 0.005
0.96 + 0.013
r= 15
Target matrix
1 1
0.67 = 0.02
0.48 + 0.02
0.24 + 0.01
0.07 = 0.01
+ 0
Random matrix
1
0.96 + 0.005
0.94 0.004
0.90 0.005
0.87 + 0.007
0.84 + 0.01
As observed from Table 5, with the increase of completeness level, the nuclear norm of the target matrix shows sharper decrease compared to the random matrix, which is consistent with the results in Figure 2.
Accuracy VS. Completeness: In Figure 6, we evaluate the completion accuracy of the proposed OCMC method across different completeness levels under fixed sampling rate. In this experiment, the target matrix is a 100 x 100 rank- 10 matrix, and the sampling rate is fixed at 25% Here, the Di method is selected as the baseline for comparison.
From the results in Figure 6, we can observe that the completion error for both models decreases as the completeness the side information increases. The error obtained by OCMC is consistently lower than that of DirtyIMC, indicating that the proposed OCMC utilize incomplete side information more effectively.
Sampling Rate for 10%-Error Completion: In Table 6, we investigate the sampling rates required by different models to achieve specific completion accuracy. It is worth noting that high accuracy is often crucial in applications such as high-precision positioning (Xiong et al., 2023) and some signal processing tasks (Zhou et al., 2023). In this experiment, we set the target completion accuracy to a relative error of 10% and compare the sampling rate needed by OCMC, DirtyIMC, and SVT under three completeness levels of side information: low (20%), medium (50%), and high (80%).
21

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
0.5
OCSC
0.4
DutSMC
0.35
Frror
0.25
0.2
0.1
67
Completeness level of Side Information
Figure 6. Error VS. Completeness level of side information with 25% sampling rate.
Table Sampling rates required by different models to achieve 10%-error under varying completeness levels of side information.
ACCURACY COMPLETENESS
SVT
MAXIDE
DIRTYIMC
OCMC
10%
LOW(20%)
0.3903
NONE
0.3402
0.3168
MEDIUM(50%)
0.3912
NONE
0.3135
0.2692
HIGH
0.3980
NONE
0.2124
0.1853
As shown in Table 6, for any given completeness level, OCMC consistently requires the fewest samples to achieve the target 10% completion error, outperforming the benchmark methods. Specifically, OCMC uses approximately 4% fewer samples on average than DMC.yIMC. In contrast, the SVT algorithm, which does not utilize side information, consistently demands more samples than both OCMC and DirtyIMC. Furthermore, the Maxide algorithm fails to reach the target accuracy across all settings, which consistent with the findings in the synthetic experiments discussed in Section 5.
To explore the robustness of the proposed OCMC under noisy side information cases, we conduct a experiment by adding different level of Gaussian noise into the incomplete side information, and compare the completion error. In our experiment, the target matrix is a 100 x 100 rank- 10 matrix, and the completeness level is 50%. The side information matrices A and B are corrupted by additive noise matrices EA and Ep, whose entries are i.i.d. N a² /m) and (0, a² /n), respectively. The results are summarized in Table 7.
Effect of Noisy Side Information:
Table 7. Completion error with varying noise level under different sampling rates.
NOISE LEVEL
Q 0
a 0.1
a 0.3
a 0.5
SAMPLIGG RATE=0.1 1
0.689
0.697
0.753
0.842
SAMPING RATE=0.15 15
0.515
0.523
0.601
0.751
SAMPLING RATE=0.2
0.319
0.324
0.422
0.551
As shown in Table 7, OCMC can still be adapted to such scenarios and maintain reasonable performance by adjusting the parameter À in (7) appropriately. In such cases, as the noise level increases, the side information becomes less helpful for matrix completion. For the extreme case when the side information is severely corrupted, we can set À 0, and the OCMC model will reduce to the standard matrix completion.
Performance under Complete Side Information: In Table 8, we compare the completion errors of OCMC and IM in recovering a 100 x 100 rank- 10 matrix with fully complete side information. Since DirtyIMC is designed for scenarios with noisy side information, we assume that the side information matrices are corrupted by Gaussian noise. Specifically, the
22

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
noise matrices A and Eg have i.i.d, entries drawn from (O, (0,3// and (O 0.12/n), respectively,
Table 8. Completion emrors of OCMC and DirtIMC with 100% complete side information.
SAMPLING RATE
0.10
0.15
0.20
0.25
0.30
0.35
0.40
OCMC DIRTYIMC
0.1359
0.0781
0.0310
0.0128
0.0083
0. 0.0062
0.0010
0.1384
0.0963
0.0329
0.0156
0.0103
0.0075
0.0032
As shown in Table 8, when the side information is complete, the proposed OCMC still outperforms DirtyIMC. However, the performance gap between DirtyIMC and OCMC is smaller compared to the case with incomplete side information (as illustrated in Figure 4). This because, for the OCMC model with complete side information, the dominance PA-B- (X) among the last three components in Table is reduced. On the other hand, the problem formulation of DirtyIMC
min || X|| M.N
Pn(AMB + N) (R)
where the matrix N represents the sum of the last three components in Table This formulation treats all three components equally. Although the contribution of P A B- (X) in the OCMC formulation becomes less dominant with complete side information, OCMC still benefits from focusing it, rather than treating all three components equally.
Notably, the OCMC model is primarily designed for scenarios with incomplete side information, which reflects most real-world situations as shown in Section 5.4. While OCMC shows reduced advantage over DirtyIMC under complete side information, it significantly improves completion accuracy and robustness when the side information is incomplete.
Complete Table for Multi-Label Learning: From the complete results in Table 9, can be observed that, among a total of 55 experimental categories, the OCMC model achieved 43 first-place rankings and 11 second-place rankings. Moreover, 43 first-place rankings and 49 second-place rankings were obtained by the OCMC. FNNC and DirtyIMC models. This further highlights the significant potential of models that account for imperfect side information in multi-label learning scenarios.
23

---

Matrix Completion with Incomplete Side Information via Orthogonal Complement Projection
Table Comparison of algorithms on all datasct with varying sampling rates wi
DATASET
w
SVT
MAXIDE
DIRTYIMC
FPC
OCMC
FNNM
ARTS
10%
0.3500
0.5746
0.4591
0.3402
0.5249
0.5126
30%
0.4639
0.6435
0.6416
0.5012
0.7206
0.6825
50%
0.6053
0.6784
0.7648
0.6103
0.8358
0.7625
70%
0.7271
0.6991
0.8584
0.7592
0.9029
0.8326
90%
0.8695
0.7135
0.9266
0.8763
0.9596
0.9115
BUSINESS
10%
0.4963
0.8614
0.6245
0.8423
0.7629
0.8425
30%
0.5806
0.8817
0.7622
0.8901
0,9159
0.8952
50%
0.6932
0.8953
0,8400
0.9335
0,9531
0,9312
70%
0.7840
0.9038
0.8942
0.9612
0.9751
0.9580
90%
0.9190
0.9092
0.9345
0.9724
0.9866
0.9769
COMPUTERS
10%
0.3594
0.6600
0,4165
0.5721
0,5796
0.5782
30%
0.4602
0.7254
0.5642
0.6610
0.7626
0.7236
50%
0.5868
0.7586
0.6900
0.7381
0.8594
0.8023
70%
0.7271
0.7796
0.7973
0.8131
0.9229
0.9036
90%
0.8471
0.7941
0.8857
0.8863
0.9608
0.9236
ENTERTAINMENT
10%
0.3623
0.6528
0.5274
0.3602
0.5867
0.5768
30%
0.5134
0.6758
0.6975
0.4822
0.7527
0.7126
50%
0.6158
0.7222
0.8058
0.6153
0.8634
0,8036
70%
0.7321
0.7566
0.8861
0.7352
0.9205
0,8623
90%
0.8392
0.7775
0.9433
0,8562
0.9598
O. 0.9026
EDUCATION
10%
0.3791
0.6001
0,4994
0,4152
0,5637
0.5523
30%
0.4919
0,6569
0.6767
0.5274
0.7170
0.6823
50%
0.5975
0.6870
0.7915
0.6322
0.8294
0.7625
70%
0.7429
0.7163
0.8787
0.7523
0.9056
0.5426
90%
0.8547
0.7280
0.9384
0.8463
0.9521
0.9036
HEALTH
10%
0.4623
0.7472
0,5185
0.4891
0.6459
0.6437
30%
0.5409
0.7974
0.6800
0.6102
0.8225
0.7982
50%
0.6332
0.8207
0.7853
0.7143
0.9067
0.8523
70%
0.7521
0.8357
0.8663
0.8059
0.9483
0.8962
90%
0.8513
0.8469
0,9267
0,8853
0,9724
0,9470
REFERENCE
10%
0.3152
0.6494
0.4899
0.3132
0.5510
0.5260
30%
0.4836
0.7285
0.6556
0.4317
0.7424
0.7132
50%
0.5985
0.7663
0.7678
0.5733
0.8436
0.8211
70%
0.7225
0.7907
0.8567
0.7082
0,9143
0.8652
90%
0.8385
0.8087
0.9280
0.8372
0.9501
0.9125
RECREATION
10%
0.3574
0.5859
0.4847
0.3982
0.5301
0.5241
30%
0.4356
0.6694
0.6652
0,5152
0.7126
0.6782
50%
0.5726
0.7103
0.7852
0.6306
0.8271
0.7721
70%
0.7154
0.7364
0.8732
0.7532
0,9071
0.8623
90%
0.8352
0.7545
0.9360
0.8643
0.9520
0.9152
SOCIAL
10%
0.3851
0.7472
0.4855
0.2365
0.6432
0.6105
30%
0.5149
0.7975
0,6508
0.3823
0.7744
0,7685
50%
0.6248
0,8207
0.7650
0.5309
0.8769
0.8362
70%
0.7261
0.8357
0,8552
0.6656
0.9356
0.8742
90%
0.8424
0.8469
0.9243
0.8212
0.9648
0.9322
SCIENCE
10%
0.2736
0.5321
0,3970
0,2512
0.4625
0,4352
30%
0.4159
0.6338
0,5811
0,4283
0.6811
0,6251
50%
0.5624
0.6831
0.7173
0.5572
0.8019
0.7325
70%
0.7027
0.7153
0.8277
0.6971
0.8961
0.8251
90%
0.8374
0.7372
0,9124
0.8352
0.9443
0.8996
SOCIETY
10%
0.3513
0,5989
0.4811
0.2752
0.5457
0.5412
30%
0.4523
0.6657
0.6474
0.4285
0.7152
0.6852
50%
0.5963
0.7036
0.7665
0.5606
0.8268
0.7652
70%
0.7024
0.7281
0.8572
0.6983
0.9010
0.8365
90%
0.8462
0.7459
0.9258
0.8256
0.9507
0.9021
24


Reviews:
[{"review_id": "zs9JQs7wAu", "reviewer": "Reviewer_zbWg", "summary": "This paper addresses matrix completion with incomplete side information. The authors propose an Orthogonal Complement Matrix Completion (OCMC) model that leverages orthogonal complement projection derived from available side information. The key insight is that when side information is incomplete, focusing on the orthogonal complement projection provides valuable constraints. The authors formulate this as minimizing both the nuclear norm of the entire matrix and the nuclear norm of its orthogonal complement projection. Using PAC learning theory, they demonstrate that sample complexity decreases quadratically with the completeness level of side information. They develop a linearized Lagrangian algorithm to efficiently solve the model with convergence guarantees. Experiments on synthetic data, multi-label learning tasks, and movie recommendations show that OCMC consistently outperforms other methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the reviewer about the constructive questions. We have addressed all the questions point by point in the following response.\n\n**Q1: Setting of the parameter $\\lambda$  when  completeness level of side information is unknown.**\n\nA1:The relation between $\\lambda$ and completeness level is discussed in Section 2.2. As the completeness increases, we need to set a larger $\\lambda$ to further restrict the rank of the complement projection. Since $\\lambda$ is a hyper-parameter, in practice, we recommend cross-validation to fine-tune the setting of $\\lambda$.\n\n**Q2: Effect of noisy side information on OCMC's performance.**\n\nA2: We agree that noisy side information can affect the performance of OCMC. However, by appropriately adjusting $\\lambda$, OCMC can still be adapted to such scenarios and maintain reasonable performance.  \n\nAs shown in (7), the OCMC formulation is$$\n\\min\\_{X} ||X||\\_* +\\lambda ||P\\_{{A}^{\\perp}{B}^{\\perp}}(X)||\\_*  \n\\quad \\text{s.t. } P\\_{\\Omega}(X)=P\\_{\\Omega}(R).$$\nWhen the side information is noisy—e.g., when matrices $A$ and $B$ are perturbed—we denote the noisy versions as $\\check{A}$ and $\\check{B}$. In such cases, the complement projection of target matrix $R$ may not lie close to the subspace $P_{\\check{A}^{\\perp}\\check{B}^{\\perp}}$, leading to a potentially large value of $||P_{\\check{A}^{\\perp}\\check{B}^{\\perp}}(R)||_*$.\n\nTo address this issue, we suggest reducing $\\lambda$ in (7) when side information becomes unreliable due to noise. In such cases, as the noise level increases, the side information becomes less helpful for matrix completion. For the extreme case when the side information is severely corrupted, we can set $\\lambda=0$, and the OCMC model will reduce to the standard matrix completion:\n$$\n\\min\\_{X} ||X||\\_* \\quad\n\\text{s.t. } P_{\\Omega}(X)=P_{\\Omega}(R).\n$$\n\nTo illustrate the performance of OCMC under the noisy side information, we compared the completion error under different noise levels. In our experiment, the target matrix is a 100 $\\times$ 100 rank-10 matrix, and the completeness level is 50%. The side information matrices $ A $ and $ B $ are corrupted by additive noise matrices $E_A$ and $E_B$, whose entries are i.i.d. $\\mathcal{N}(0, \\alpha^2/m)$ and $\\mathcal{N}(0, \\alpha^2/n)$, respectively.\n|Noise level|$\\alpha=0$|$\\alpha=0.1$|$\\alpha=0.3$|$\\alpha=0.5$|\n|-|-|-|-|-| \n|Observation rate=0.1|0.689|0.697|0.753|0.842|\n|Observation rate=0.15|0.515|0.523|0.601|0.751|\n|Observation rate=0.2|0.319|0.324|0.422|0.551|\n\nIt can be observed that across noise levels, OCMC achieves slightly lower yet still robust MSE.\nWe will include these discussions in the final submission. \n\n**Q3: Discussions about the OCMC's computational complexity.**\n\n A3: For a target matrix $R \\in \\mathbb{R}^{m\\times n}$  and side information $A\\in\\mathbb{R}^{m\\times d}$, $B \\in \\mathbb{R}^{n\\times d}$ \n (for convenience, here we assume $r_A=r_B=d$), the per-iteration complexity of the linear-ADMM algorithm for OCMC consists of three parts:\n- Calculating $P_{A^\\perp B^\\perp}(X): O(\\min(dmn+dm^2, dmn+dn^2))$.\n- Singular Value Thresholding (SVT): $O(\\min(m^2n, n^2m))$.\n- Matrix inner product: $O(mn)$.\n\nThe total complexity is dominated by the SVT step, i.e., $O(\\min(m^2n, n^2m))$. For large-scale problems, we can replace the full SVD in SVT with more efficient methods, such as randomized SVD and Lanczos method, whose complexities are $O(mn+r^2m+r^3)$ and $O(rmn)$, respectively, where $r$ is rank of $R$.  \n\n**Q4: Some comments on the neural network-based approaches.**\n\n A4:  We agree that neural network-based approaches, such as GCMC[1] or LightGCN [2], have been widely applied to solve similar problems in recommendation systems. These methods can achieve good performance in certain scenarios. However, they often come with high training overhead, especially when dealing with large-scale user and item sets. Moreover, due to the lack of interpretability, these models may suffer from poor generalization ability [3,4]. According to Occam's Razor, simpler models with fewer assumptions tend to generalize better. This motivates our focus on theoretically grounded, interpretable methods with lower complexity.\n\nIn our future work, we also plan to explore the integration of the OCMC into neural network-based approaches, aiming to better incorporate side information and enhance the performance. These discussions will be included in our final submission.\n\n**Q5: Essential References Not Discussed.**\n\n A5:  We are happy to include these in our final submission.\n\nWe hope the above analysis and results sufficiently address the reviewer’s comments.\n\n**References**:\n\n[1] Graph Convolutional Matrix Completion. KDD, 2018.\n\n[2] Lightgcn: Simplifying and powering graph convolution network for recommendation. SIGIR, 2020.\n\n[3] Explicit factor models for explainable recommendation based on phrase-level sentiment analysis SIGIR, 2015.\n\n[4] Explainable recommendation: A survey and new perspectives. FnTIR, 2020.", "claims_and_evidence": "The claims in this paper are supported by evidence:\n- The claim that orthogonal complement projection plays a critical role is supported by theoretical analysis in Section 2.2 and empirical evidence in Figure 2, showing that both the rank and nuclear norm of this projection decrease with increasing side information completeness. \n- The sample complexity analysis (Corollary 3.4) rigorously establishes the quadratic decrease with the completeness level.\n- Performance claims are backed by comprehensive experiments across different completeness levels, observation rates, and real-world applications.", "methods_and_evaluation_criteria": "The methods and evaluation criteria are appropriate for the problem:\n- The OCMC formulation captures the intuition of using incomplete side information.\n- The linearized ADMM algorithm addresses computational challenges in the optimization.\n- Evaluation spans synthetic experiments (controlling completeness and observation rates) and real-world applications.", "theoretical_claims": "The theoretical analysis using PAC learning theory appears sound:\n- The Rademacher complexity bound (Lemma 3.2) establishes the relationship with matrix dimensions and side information completeness.\n- The generalization error bound (Theorem 3.3) builds on this to bound expected recovery error.\n- The sample complexity result (Corollary 3.4) derives the relationship with completeness level.", "experimental_designs_or_analyses": "The experimental designs are sound:\n- Synthetic experiments with controlled settings allow isolation of different factors\n- Real-world experiments on well-established datasets (MovieLens-100k, Yahoo web classification)\n- Thorough ablation studies examining the relationship between completeness, observations, and accuracy", "relation_to_broader_scientific_literature": "This work extends the existing literature on conventional matrix completion and perfect side information methodologies.", "essential_references_not_discussed": "There are few other papers that studied the problem of matrix completion with graph side information and should be included in the literature review.\n- Community detection and matrix completion with social and item similarity graphs, IEEE Transactions on Signal Processing, 2021\n- The optimal sample complexity of matrix completion with hierarchical similarity graphs, ISIT 2022\n- Graph-assisted matrix completion in a multi-clustered graph model, ISIT 2022\n- On the fundamental limits of matrix completion: Leveraging hierarchical similarity graphs, IEEE Transaction on Information Theory, 2024", "other_strengths_and_weaknesses": "Strengths and weaknesses have been highlighted in other questions.", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. How would you recommend setting the parameter λ in practice when the completeness level of side information is unknown? Could this be automatically determined from the data?\n2. Beyond incompleteness, have you explored how noisy side information affects OCMC's performance? This seems particularly relevant for real-world applications.\n3. How does OCMC's computational complexity scale with matrix dimensions and side information size? Are there approximations that could be applied to very large-scale problems?\n4. Any comments on the line of research that uses neural network-based approaches to solve the same problem?", "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": "", "extra_scores": {}}, {"review_id": "tUo03oDh8d", "reviewer": "Reviewer_67wE", "summary": "In this work, the authors propose a new matrix completion method with incomplete side information. The incompleteness of the side information is defined and the solution called Orthogonal Complement Matrix Completion (OCMC) is developed. Theoretical analysis is given to show the upper bound of the errors. Experiments on various data verify the performance of the proposed OCMC method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive questions. We address them point by point below.\n\n**Q1: The effect of $P_{A^\\perp B^\\perp}(X)$ in (7) when the side information is complete.**\n\n A1: When the side information is complete, the column and row spaces of $R$ are fully contained in the column space of $A$ and row space of $B$, respectively, implying that $P_{A^\\perp B^\\perp}(R) = 0$. However, this does not mean that the second term in (7) vanishes. Instead, it will become more important in the optimization.\n \nIn (7), $\\lambda$ controls the regularization strength depending on the completeness of the side information. As discussed in Section 2.2, higher completeness → larger $\\lambda$. When the side information is complete, $\\lambda$ should be sufficiently large so that (7) becomes equivalent to a hard-constrained optimization:\n$$\n\\min_{X}||X||\\_*\\quad s.t. \\ P_{\\Omega}(X) = P_{\\Omega}(R), \\ P_{A^\\perp B^\\perp}(X) = 0. \n$$\nIn summary, when the side information is complete, the second term in (7) does not vanish but becomes stricter. \n\n**Q2: The performances of OCMC and DirtyIMC when the completeness level of side Information is 100\\%.**\n\nA2:  We compare the completion errors of OCMC and DirtyIMC in recovering a $100 \\times 100$ rank-$10$ matrix  with 100\\% complete side Information. Since DirtyIMC is designed for scenarios with noisy side information,\nwe assume that the side information matrices are corrupted by Gaussian noise.\n Specifically, the noise matrices $E_A$ and $E_B$ have i.i.d. entries drawn from $\\mathcal{N}(0, 0.1^2/m)$ and $\\mathcal{N}(0, 0.1^2/n)$, respectively.\n\n|Observation rate|0.1|0.15|0.2|0.25|0.3|0.35|0.4|\n|-|-|-|-|-|-|-|-|\n|OCMC|0.1359|0.0781|0.0310|0.0128|0.0083|0.0062|0.0010|\n|DirtyIMC|0.1384|0.0963|0.0329|0.0156|0.0103|0.0075|0.0032\n\nAs shown in the results, when the side information is complete, the proposed OCMC still outperforms DirtyIMC. However, the performance gap between DirtyIMC and OCMC is smaller compared to the case with incomplete side information (as illustrated in Figure 4). This is because, for the OCMC model with complete side information, the dominance of $P_{A^\\perp B^\\perp}(X)$ among the last three components in Table 1 of the manuscript is reduced. \nOn the other hand, for dirtyIMC:\n$$\n\\min\\_{M} ||M||\\_* + \\lambda ||N||\\_* \\quad \\text{s.t.} \\quad P_{\\Omega}(AMB^T + N) = P_{\\Omega}(R),\n$$\nthe matrix  $N$ represents the sum of the last three components in Table 1. This formulation treats all three components equally.  Although the contribution of  $P_{A^\\perp B^\\perp}(X)$ in OCMC formulation becomes less dominant with complete side information, OCMC still benefits from focusing on it, rather than treating all three components equally.\n\nIt is worth noting that our OCMC model is primarily designed for scenarios with incomplete side information, which reflects most real-world scenarios—as demonstrated by our experiments. While OCMC shows reduced advantage over DirtyIMC under complete side information, it significantly improves recovery accuracy and robustness with incomplete side information is.  \n\n**Q3: Analysis or evidence showing that the datasets match the hypotheses of incomplete side information.**\n\nA3: Thank you for raising this point. We justify the incomplete side information assumption from two perspectives:\n -  Intuitive and practical perspective:  Taking the recommendation system as an example, side information typically consists of observable attributes of users (age/gender) and items (categories/genres). However, the complete information of user preferences or item characteristics is much richer.  It includes latent factors that are not captured but still contribute to the rating matrix. Intuitively, it is also unrealistic to assume that age, gender, or category alone fully describe user behavior or item features. The same applies in multi-label learning, where side information (e.g., feature descriptors or annotations) only partially captures label dependencies. \n- Subspace-based geometric perspective: Complete side information implies that the target matrix's column/row space is contained within the subspace spanned by the given side information. However, for datasets in our experiments, this relation does not hold. A formal check for the subset relation involves computing the projection $P_A R$ and verifying if $||P_A R - R||\\_F = 0$ or close to zero, where $P_{A} = A(A^\\top A)^{-1} A^\\top$. A large value confirms the incomplete side information. \n\nThese insights affirm that side information of the practical dataset is present but not complete. \n\n**Q4: The descreiption issue in the left column of line 426, page 8.**\n\nA4: Thank you for pointing out this confusion. We agree that the original description lacked precision. We will revise it as \n> Among them, DirtyIMC, FNNM and OCMC are applicable for matrix completion with incomplete side information.\n\nin the final version.\n\nWe hope the above analysis and results sufficiently address the reviewer’s comments.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I roughly check the correctness of the proof of Lemma 3.2 and related discussions about the number of observations. No big issues found.", "experimental_designs_or_analyses": "Yes, I've checked the experimental results on synthetic data and real datasets (MLL and MovienLens). No big issues found.", "relation_to_broader_scientific_literature": "A new problem for matrix completion --- completion with 'incomplete side information' is defined and analyzed. It seems to be reasonable in real data, and the experiments also verify the performance (but lack of verifying whether the real data has incomplete side information)", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\nProper problem definition and analysis on incomplete side information. \n\nWeakness:\n\nLack of verification on the incompleteness of the side information in the real dataset.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. As Fig.2 shows, when the side information is complete. $\\mathbb{P}_{A^\\perp B^\\perp}(\\mathbf{R})$ will be zero. Thus, the second term in Eq.(7) seems to vanish, such that no side information is used. Could the author explain it? \n\n2. In the synthetic data experiment (Fig.4 and 6), how about the performance when the completeness level of side Information is 100%? In this case, the side information is complete, so will the performance of OCMC be the same as dirtyIMC? If not, what causes the difference?\n\n3. Two experiments on real dataset show the superior performance of the proposed method. However, there is a lack of analysis or evidence showing that the datasets match the hypotheses of incomplete side information. Therefore, it is unclear that the improvement on these datasets comes from properly dealing with the incomplete side information.\n\n4. In the left column of line 426, page 8, 'Among them, dirtyIMC, FNNM, and OCMC, as models designed for incomplete side information....', it is confusing that dirtyIMC and FNNM only deal with imperfect(noisy) side information, not incomplete side information.", "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": "", "extra_scores": {}}, {"review_id": "zrMGca8AW2", "reviewer": "Reviewer_hL9t", "summary": "This paper studies the problem of matrix completion with side information. When the side information is not complete, the authors propose to use orthogonal complement projection to minimize the signals outside the side information, instead of constraining the recovered matrix in the space spanned by side information. The authors developed an ADMM algorithm to solve the proposed target with convergence guarantees. The theoretical investigation shows that the sample complexity decreases quadratically with the completeness level under the completeness level. The practical performance is examined on both synthetic and real data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive comments. We address all questions point by point below.\n\n**Q1: How are representative algorithms selected? Is there a SOTA method for each dataset?**\n\nA1: For each dataset, we emphasize the comparison within the scope of matrix completion methods. To ensure a comprehensive evaluation, we have carefully reviewed the existing literature and selected SOTA matrix completion algorithms as baselines, to the best of our knowledge.\n- Movielens-100k: FNNM [1] is recognized as a leading matrix completion method.  \n- Multilabel learning: Both DirtyIMC [1,2] and FNNM demonstrate near-SOTA performance.  \n- Effectiveness and Robustness validation: We compared against classical algorithms without side information (SVT, FPC) and Maxide from IMC framework.\n\nThe selection of representative algorithms ensures that our comparisons are both meaningful and rigorous in addressing the core issue of matrix completion with incomplete side information.\n\n**Q2: Does generalization of $B$ in Section 5.1 follow a similar transformation like $A$?**\n\nA2: Yes, the generation of $B$ is similar to that of $A$. Specifically, $B=VQ$, following the similar transformation as $A=UT$ in Section 5.1, where $Q$ is a random matrix generated similarly to $T$.\n\n**Q3: In Fig 2, what's rationale of a decreasing trend in nuclear norm of a random matrix?**\n\nA3: The operator $P_{A^{\\perp}B^{\\perp}}$ satisfies the property  $||P_{A^{\\perp}B^{\\perp}}(X)||\\_* \\leq ||X||\\_*$, as orthogonal projection typically reduces the nuclear norm.  Furthermore, as side information becomes more complete, the dimension of the projected subspace shrinks. Specifically, the subspace defined by $P\\_{\\check{A}^{\\perp} \\check{B}^{\\perp}}(\\cdot)$ is a subset of that by $P\\_{{A}^{\\perp} {B}^{\\perp}}(\\cdot)$,  leading to $||P_{\\check{A}^{\\perp} \\check{B}^{\\perp}}(X)||_\\* \\leq ||P\\_{A^{\\perp}B^{\\perp}}(X)|| _\\*  $, explaining the decrease trend.\n\n**Different Decreasing Rates of $X$ and $R$ in Fig 2**: For a random matrix, its row and column subspaces are uniformly distributed over the full space.  When a random matrix $X$ is projected by $P_{A^{\\perp}B^{\\perp}}$, where $A$ and $B$ are derived from the row and column subspaces of the target matrix $R$, the nuclear norm of projection decreases approximately at a rate of $1/n$.  In contrast, for $R$, since the projection is constructed based on its own subspaces, the decay is faster at approximately $1/r$. \n\nAs suggested, we have added experiments with different ranks and the corresponding nuclear norm results are as follows.\n||Completeness level|0|0.2|0.4|0.6|0.8|1|\n|-|-|-|-|-|-|-|-|\n|r=5|target matrix|1±0|0.66±0.05|0.40±0.03|0.22±0.03|0.08±0.01|0±0|\n|r=5|random matrix|1±0|0.99±0.004|0.98±0.007|0.97±0.005|0.96±0.013|0.94±0.01|\n|r=15|target matrix|1±0|0.67±0.02|0.48±0.02|0.24±0.01|0.07±0.01|0±0|\n|r=15|random matrix|1±0|0.96±0.005|0.94±0.004|0.90±0.005|0.87±0.007|0.84±0.01|\n\nAs observed from the table above, with the increase of completeness level, the nuclear norm of the target matrix shows a sharper decrease compared to the random matrix.\nThese results will be included in the final submission.\n\n**Q4: Assumption of Theorem 3.3 regarding the distribution of sampling distribution in page 6.**\n\nA4: Thanks for pointing out this confusion. The statement \"our analysis makes no assumptions regarding the distribution of observed entry positions\" means that Theorem 3.3 provides a generalization error bound that holds under any sampling distributions. It is important to note that the definition of the generalization error $L(X)$ depends on the given sampling distribution, i.e.,  \n$$\nL(X)=E_{(i,j)\\sim p}[l(X_{ij},R_{ij})].\n$$\nIn particular, for squared loss under uniform sampling, $L(X)$ corresponds to the mean squared error (MSE): \n$$\nMSE(X)=E_{(i,j)\\sim U}[(X_{ij}-R_{ij})^2].\n$$\nWe believe the reviewer’s concern is how the distribution-free bound on $L(X)$ connects to MSE, given that MSE is a key metric in matrix completion. Under the squared loss, the difference between $L(X)$ and MSE is that $L(X)$ is expectation under an arbitrary sampling distribution $p$, while MSE assumes uniform. From Theorem 3.3, denote the bound of $L(X)$ as $W$, then  \n$$\nL(X)=E_{(i,j)\\sim p}[(X_{ij}-R_{ij})^2]\\leq W.\n$$\nApplying the total variation distance bound on expectation for discrete distributions, we obtain:  \n$$\nE_{(i,j)\\sim U}[(X_{ij}-R_{ij})^2]\\leq E_{(i,j)\\sim p}[(X_{ij}-R_{ij})^2]+2M\\cdot TV(U, p) \\le W+2M\\cdot TV(U, p) \n$$\nwhere $M$ is the upper bound of $(X_{ij}-R_{ij})^2$, and $TV(U, p)$ represents the total variation distance between the uniform and arbitrary sampling distributions. This result extends our bound to MSE under arbitrary sampling distributions.\n\nWe hope that the above analysis and experimental results adequately address the reviewer’s comments.\n\n**References:**  \n[1] Feature and nuclear norm minimization for matrix completion. IEEE TKDE, 2020.  \n[2] Matrix completion with noisy side information. NIPS, 2015.", "claims_and_evidence": "The claims are sound, and supported by theoretical investigations and experimental evidence.", "methods_and_evaluation_criteria": "How are representative algorithms selected for comparison purpose? Is there a SOTA method for each dataset?", "theoretical_claims": "I didn't go through the detailed proof, but the analysis is standard in PAC framework, and is sound to me. \n\nThe major question is about the interpretation of conditions. The assumptions on missing mechanism are unclear. The authors claim that the theory doesn't makes no assumptions regarding the distribution of observed entry positions. But it seems that a minimal observation probability among all entries is needed. It would be better to discuss how those conditions translate to requirements on missing mechanism and discuss applicability from there.", "experimental_designs_or_analyses": "In Figure 2, what's rationale of a decreasing trend in nuclear norm of a random matrix? It would be better to include an error bar, and vary ranks for a more complete message. It also helps motivate why minimizing part 4 (described in Figure 3) is effective.\n\nHow is matrix $B$ generated in Section 5.1? Does that follow a similar transformation like $A$?", "relation_to_broader_scientific_literature": "Matrix completion has a broad range of applications, such as collaborative filtering, computer vision, and recommendation systems.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates matrix completion with side information associated with both columns and rows. The authors introduce the Orthogonal Complement Matrix Completion model, which decomposes the target matrix into a combination of signals that can be explained by the side information and signals not explainable by them. To mitigate the ill-posedness of matrix recovery due to missing entries, the low-rank assumption is imposed, particularly crucial for recovering signals not explained by the side information. Theoretical analysis of the error bound is provided.

All reviewers voted positively on this submission. The reviews are positive about the proposed decomposition model and indicate that the claims are largely supported by theoretical and empirical evidence. However, several reviewers raised questions and concerns. Reviewer zbWg identified several missing references. Reviewer 67wE requested verification of the incompleteness of the side information in the real dataset. (The authors have acknowledged the existence of numerical evidence in the rebuttal, which should be included in the revised paper.) Reviewer posed several clarification questions, primarily concerning missing structure.

Based on these comments, the authors should revise their work accordingly. However, based on my judgement, additional review is not needed to reach an acceptance recommendation. Therefore, I recommend accepting the paper.
Decision: Accept (poster)