<?xml-model href='http://www.tei-c.org/release/xml/tei/custom/schema/relaxng/tei_all.rng' schematypens='http://relaxng.org/ns/structure/1.0'?><TEI xmlns="http://www.tei-c.org/ns/1.0">
	<teiHeader>
		<fileDesc>
			<titleStmt><title level='a'>High-Rank Matrix Completion with Side Information</title></titleStmt>
			<publicationStmt>
				<publisher></publisher>
				<date>2018</date>
			</publicationStmt>
			<sourceDesc>
				<bibl> 
					<idno type="par_id">10063418</idno>
					<idno type="doi"></idno>
					<title level='j'>AAAI Conference on Artificial Intelligence</title>
<idno></idno>
<biblScope unit="volume"></biblScope>
<biblScope unit="issue"></biblScope>					

					<author>Y. Wang</author><author>E. Elhamifar</author>
				</bibl>
			</sourceDesc>
		</fileDesc>
		<profileDesc>
			<abstract><ab><![CDATA[We address the problem of high-rank matrix completion with side information. In contrast to existing work dealing with side information, which assume that the data matrix is low-rank, we consider the more general scenario where the columns of the data matrix are drawn from a union of low-dimensional subspaces, which can lead to a high rank matrix. Our goal is to complete the matrix while taking advantage of the side information. To do so, we use the self-expressive property of the data, searching for a sparse representation of each column of matrix as a combination of a few other columns. More specifically, we propose a factorization of the data matrix as the product of side information matrices with an unknown interaction matrix, under which each column of the data matrix can be reconstructed using a sparse combination of other columns. As our proposed optimization, searching for missing entries and sparse coefficients, is non-convex and NP-hard, we propose a lifting framework, where we couple sparse coefficients and missing values and define an equivalent optimization that is amenable to convex relaxation. We also propose a fast implementation of our convex framework using a Linearized Alternating Direction Method. By extensive experiments on both synthetic and real data, and, in particular, by studying the problem of multi-label learning, we demonstrate that our method outperforms existing techniques in both low-rank and high-rank data regimes]]></ab></abstract>
		</profileDesc>
	</teiHeader>
	<text><body xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink">
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Introduction</head><p>Matrix completion, which is the problem of estimating missing entries of an incomplete matrix, is a fundamental task in machine learning with numerous applications, including, collaborative filtering for recommender systems <ref type="bibr">(Rennie and Srebro 2005;</ref><ref type="bibr">Sindhwani et al. 2010)</ref>, multi-label learning (Natarajan and Dhillon 2014; <ref type="bibr">Xu, Jin, and Zhou 2013;</ref><ref type="bibr">Argyriou, Evgeniou, and Pontil 2008)</ref>, semi-supervised clustering <ref type="bibr">(Chiang et al. 2014</ref>) and global positioning <ref type="bibr">(Singer and Cucuringu 2010;</ref><ref type="bibr">Singer 2008;</ref><ref type="bibr">Biswas et al. 2006)</ref>. Existing algorithms that deal with missing entries in data can be divided into two main categories. The first group of algorithms, such as Probabilistic PCA (PPCA) (Tipping and Bishop 1999b), Factor Analysis (FA) <ref type="bibr">(Knott and Bartholomew 1999)</ref> and Convex Low-Rank Matrix Completion <ref type="bibr">(Candes and Recht 2009;</ref><ref type="bibr">Keshavan, Montanari, and Oh</ref> Matrix Completion with Side Information. In many realworld problems, we have access to additional information about the entries of the data matrix, referred to as side information, which can guide the matrix completion in order to obtain more accurate solutions <ref type="bibr">(Adams, Dahl, and Murray 2010;</ref><ref type="bibr">Agarwal and Chen 2009;</ref><ref type="bibr">Menon et al. 2011a;</ref><ref type="bibr">Porteous, Asuncion, and Welling 2010)</ref>. For example, in the classical Netflix problem, which aims to predict the unobserved entries of a users-movies rating matrix, besides the rating history, we have access to information/features of users, such as age, gender, etc., as well as information/features of movies, such as suspense, science fiction, etc. Also, in the multi-label learning problem, whose goal is to find all relevant labels to each sample, in addition to the incomplete observed labels, the features describing instances are often given at the same time. Indeed, such side information can be leveraged in matrix completion for better recovery performance, especially, when very few matrix entries are observed.</p><p>Despite its significance, the problem of matrix completion with side information has only been recently studied, where all existing techniques have addressed the problem when the data matrix is low-rank <ref type="bibr">(Goldberg et al. 2010;</ref><ref type="bibr">Menon et al. 2011b;</ref><ref type="bibr">Natarajan and Dhillon 2014;</ref><ref type="bibr">Jain and Dhillon 2013;</ref><ref type="bibr">Xu, Jin, and Zhou 2013;</ref><ref type="bibr">Chiang, Hsieh, and Dhillon 2015;</ref><ref type="bibr">Lu et al. 2016;</ref><ref type="bibr">Chiang, Hsieh, and Dhillon 2016;</ref><ref type="bibr">Liu and Li 2016)</ref>. The methods in <ref type="bibr">(Menon et al. 2011b;</ref><ref type="bibr">Natarajan and Dhillon 2014)</ref> cast the problem as finding a factorization of data matrix as the inner product of side information features with the product of two unknown matrices that must be recovered simultaneously, and employ a nonconvex algorithm to recover the unknowns. Although experimental results have shown favorable results, the proposed methods rely on non-convex programming and depend on good initialization. The methods in <ref type="bibr">(Jain and Dhillon 2013;</ref><ref type="bibr">Xu, Jin, and Zhou 2013)</ref> use side information feature matrices, F c and F r , for the rows and columns of the data matrix, Y , in a so called Inductive Matrix Completion (IMC) framework. More specifically, assuming that all columns and rows of the data matrix lie in spaces spanned, respectively, by the column vectors in F c and F r , <ref type="bibr">(Jain and Dhillon 2013;</ref><ref type="bibr">Xu, Jin, and Zhou 2013)</ref> consider a factorization of Y as Y = F r QF &gt; c for an unknown low-rank inductive matrix Q and try to complete the data by finding Q. While (Jain and Dhillon 2013) uses a low-rank matrix factorization, <ref type="bibr">(Xu, Jin, and Zhou 2013)</ref> proposes a method, referred to as Maxide, that directly minimizes the rank of Q based on a singular value thresholding algorithm. The work in <ref type="bibr">(Chiang, Hsieh, and Dhillon 2015)</ref> considers an extension of the IMC framework, referred to as DirtyIMC, to addresses the problem of matrix completion with noisy side information. More specifically, it considers the model Y = F r QF &gt; c + R, where the residual matrix R is used to capture the component of the data that the side information cannot describe, and requires both Q and R to be low-rank, hence assuming a low-rank data matrix, Y . The work in <ref type="bibr">(Lu et al. 2016</ref>) considers a modification of IMC by assuming that the inductive matrix Q is sparse, instead of low-rank, to deal with the situation that Q in not necessarily low-rank. Hence, it minimizes the rank of Y while minimizing the sparsity of Q. We refer to this method as Sparse Interactive Model (SIM) in our paper.</p><p>It is important to note that all the above work, which address the problem of matrix completion with side information, consider the setting where the data matrix is low-rank. On the other hand, as discussed earlier, in many real-world problems, the data matrix columns or rows lie in a union of low-dimensional subspaces which leads to a high-rank data matrix. As a result, existing techniques will not be effective, as we will demonstrate in our experiments.</p><p>Paper Contributions. In this paper, we address the challenging and general problem of high-rank matrix completion with side information. Building on <ref type="bibr">(Elhamifar and Vidal 2013;</ref><ref type="bibr">2009)</ref>, we assume that each column of the data matrix can be efficiently represented as a sparse combination of a few other columns, which holds for both a single subspace as well as a union of subspaces. We cast the problem as recovering the missing entries and sparse representation coefficients, while taking advantage of the side information to complete the data matrix. More specifically, we propose a factorization of the data into a product of side information matrices with an unknown interaction matrix, under which each column of the data matrix can be recon-structed using a sparse combination of its other columns. As our proposed formulation is non-convex and NP-hard, building on <ref type="bibr">(Elhamifar 2016)</ref>, we propose a lifting framework, where we couple sparse coefficients and missing values and define an equivalent optimization that is amenable to convex relaxation. We derive a convex optimization and propose an efficient implementation of our framework using a Linearized Alternating Direction Method (LADM) <ref type="bibr">(Yang and Yuan 2013)</ref>, which is significantly faster than standard alternating direction methods, hence, allowing to efficiently deal with large data and high percentage of missing entries. Finally, by extensive experiments on synthetic and real data, in particular, by studying the problem of multi-label learning, we demonstrate that our method outperforms existing techniques in both low-rank and high-rank data regimes.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>High-Rank Matrix Completion with Side Information</head><p>In this section, we propose a method to address the problem of high-rank matrix completion with side information. Assume that we are given a data matrix Y 2 R n&#8677;N , which is partially observed, where &#8486; and &#8486; c denote, respectively, the set of indices of observed and missing entries of Y . Assume that every row and column of Y is associated with an observed feature vector, providing side information. Let F r 2 R n&#8677;kr and F c 2 R N &#8677;kc denote side information matrices of feature vectors associated, respectively, with the rows and columns of Y . We refer to F r and F c as row and column space side information matrices, as they provide additional information about the relationships between entries of the data matrix, which we will use for data completion.</p><p>In this paper, we consider a general high/full rank model for Y by assuming that the columns (or similarly rows) of Y lie in a union of low-dimensional subspaces. Our goal is to find missing entries of Y , while taking advantage of the side information and respecting the underlying model of the data matrix. While the problem of matrix completion with side information has been studied before <ref type="bibr">(Goldberg et al. 2010;</ref><ref type="bibr">Menon et al. 2011b;</ref><ref type="bibr">Natarajan and Dhillon 2014;</ref><ref type="bibr">Jain and Dhillon 2013;</ref><ref type="bibr">Xu, Jin, and Zhou 2013;</ref><ref type="bibr">Chiang, Hsieh, and Dhillon 2015;</ref><ref type="bibr">Lu et al. 2016;</ref><ref type="bibr">Chiang, Hsieh, and Dhillon 2016;</ref><ref type="bibr">Liu and Li 2016)</ref>, all existing research has focused on the case where the data matrix is low-rank. On the other hand, in this paper, we study and address the more challenging problem of high-rank matrix completion with side information, which covers the low-rank setting as a special case.</p><p>To tackle the problem, similar to all conventional methods (Natarajan and Dhillon 2014; <ref type="bibr">Jain and Dhillon 2013;</ref><ref type="bibr">Xu, Jin, and Zhou 2013;</ref><ref type="bibr">Chiang, Hsieh, and Dhillon 2015;</ref><ref type="bibr">Lu et al. 2016;</ref><ref type="bibr">Chiang, Hsieh, and Dhillon 2016;</ref><ref type="bibr">Liu and Li 2016)</ref>, we assume that the columns and rows of Y lie in spaces spanned by the columns of F r and F c , respectively. Thus, we can write Y = F r QF &gt; c , where Q 2 R kr&#8677;kc is a unknown interaction matrix. Let &#562; 2 R n&#8677;N denote the zero-filled data matrix, where the missing entries are filled with zeros. Our goal is to find the complete matrix Y , so that it can be decomposed as Y = F r QF &gt; c and the entries of Y indexed by &#8486; coincide with the entries of &#562; , i.e., R &#8486; (Y )=R &#8486; ( &#562; ). The function R &#8486; (Y ) returns a matrix whose (i, j)-th entry is Y i,j when (i, j) 2 &#8486; and is 0 otherwise. When the number of observed entries is small, in particular when |&#8486;| &lt;k r k c , without priors on Q and Y the problem has infinitely many solutions for unknown variables. Thus, in addition to utilizing side information, we need to impose appropriate priors on the unknown parameters and use the underlying structure of the data in order to perform data completion.</p><p>To take advantage of the fact that the columns of the data matrix Y lie in a union of subspaces, we use the Self-Expressive Model (SEM) <ref type="bibr">(Elhamifar and Vidal 2013;</ref><ref type="bibr">Elhamifar 2016)</ref>, which states that each column of the data matrix can be written as a sparse representation of the other columns, hence, Y = YC, where C 2 R N &#8677;N denotes the self-representation coefficient matrix. In addition, we need to impose diag(C)=0 to remove the trivial solution of writing each point as a combination of itself. Notice that the SEM covers both a single and a union of low-dimensional subspaces, since in each subspace of dimension d, every point can be written as a combination of only d other points, in general positions, from the same subspace. Thus, to solve the problem of high-rank matrix completion with side information, we propose to solve</p><p>where kCk 0 indicates the `0-norm of C, counting the number of non-zero elements, and h(&#8226;) is an appropriate prior on the interaction matrix Q, which will be discussed shortly. Notice that the optimization in (1) is NP-hard and nonconvex, due to the product of unknown matrices Y and C as well as the sparsity regularization on C. To tackle the problem, building on <ref type="bibr">(Elhamifar 2016)</ref>, we propose a lifting scheme, where we define new optimization variables, corresponding to the product of unknown coefficients and the missing values, and pose the problem as an optimization on the new variables that, together with appropriate constraints, will lead to an equivalent optimization to (1).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Lifting-Based Formulation</head><p>In this part, we develop an equivalent optimization for our formulation in (1) and propose an efficient convex relaxation. We denote by y i , &#563;i 2 R n the i-th column of Y and &#562; , respectively. We also denote by &#8486; i , &#8486; c i &#10003; {1,...,n} the set of, respectively, observed and missing entries of the i-th column of Y . Denoting by U &#8486; c i 2 R n&#8677;|&#8486; c i | a matrix formed by taking the columns of the identity matrix indexed by &#8486; c j , we can write</p><p>where x i 2 R |&#8486; c i | denotes the vector of missing values of the i-th column of the data matrix. Denoting the element (i, j) of C by c i,j , using equation (2), we can rewrite the self-expressiveness model, y j = P N i=1 c i,j y i , as</p><p>Given the fact that y j is the j-th column of Y , using the above, we can write</p><p>where the dictionary D is a given and known matrix and is defined, using the zero-filled data and the columns of the identity matrix indexed by missing entries of points, as</p><p>while the matrix A, which consists of missing entries and self-representation coefficients, is unknown and defined as</p><p>It is important to notice that each A i is a rank-1 matrix, since we can write it is as the outer product of vectors</p><p>. This helps us to pave the way for an equivalent optimization to (1) that is amenable to convex relaxation. More specifically, if we define each A i as</p><p>and impose that rank of A i be one, we obtain &#945; i,j = c i,j x i .</p><p>As a result, we can write our proposed optimization in (1) as the equivalent optimization program</p><p>Here, A (c) denotes a submatrix of A, whose i-th row corresponds to the first row of A i , i.e., A (c) = C. Notice that we have transferred the non-convexity of the product of unknown coefficients and missing entries in (1) to a set of rank-1 constraints on the new optimization variables. As we show next, our new formulation in (8) allows to explore efficient methods based on convex relaxation to solve the problem.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Convex Relaxation and Extensions</head><p>To obtain a convex optimization, first we use the convex surrogate of the `0-norm, and minimize the `1-norm kA (c) k 1 . In the paper, we select the prior on Q to be h(Q)= 1/2kQk 2 F . Also, we use the nuclear norm relaxation of the rank constraints, i.e., we use kA i k &#8676; &#63743; &#8984;, for &#8984; &gt; 0, where the nuclear norm kA i k &#8676; is defined as the sum of the singular values of A i . To reduce the number of constraints, we bring the nuclear norm constraints to the objective function via a regularization parameter &#8674; &gt; 0 and propose to solve</p><p>Notice that the above optimization is convex, which can be solved efficiently using convex programming techniques.</p><p>In real-world problems, however, observed data entries are corrupted by noise <ref type="bibr">(Soltanolkotabi, Elhamifar, and Candes 2014)</ref>. In other words, we have R &#8486; ( &#562; )=R &#8486; (Y +E 1 ), for an error matrix E 1 . Moreover, since error-free data may not necessarily lie perfectly on subspaces, we should account for deviations from the SEM model, i.e., &#562; = Y +E 2 , for an error matrix E 2 . We assume that the energy of the noise terms are bounded, i.e., kE 1 k 2 F &#63743; &#8675; 1 and kE 2 k 2 F &#63743; &#8675; 2 for &#8675; 1 &gt; 0 and &#8675; 2 &gt; 0. Thus, using the Lagrange multipliers, we propose to solve</p><p>where &#181; 1 ,&#181; 2 &gt; 0 are positive regularization parameters.</p><p>Next, we develop an efficient algorithm to solve our proposed optimization in (10).</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Linearized ADM Algorithm</head><p>In this section, we develop a Linearized Alternating Direction Method (LADM) <ref type="bibr">(Yang and Yuan 2013)</ref> to efficiently solve (10). To do so, we introduce two auxiliary matrices Z and V , which we enforce to be equal to A, and define the notations of submatrices V i and Z (c) similar to ( <ref type="formula">7</ref>) and ( <ref type="formula">8</ref>), respectively. We consider the following optimization,</p><p>which is equivalent to (10). To solve the above optimization via the LADM approach, we first form the augment Lagrangian function of (11), which is</p><p>where &#915; 1 , &#915; 2 and &#915; 3 are Lagrange multiplier matrices associated with the constraints of (11), and &gt; 0 is the augmented Lagrangian penalty parameter.</p><p>In an ADM framework, we take an iterative approach, where starting from initialization of optimization matrices, we fix all unknown matrices except one, solve for the unknown matrix, and repeat this procedure for every optimization matrix. It is straightforward to verify that the updates of A and Q depends on the updates of Y , Z and V and vice versa. To derive the updates, we perform the following.</p><p>-At iteration k +1, minimizing L with respect to A, while fixing other matrices, leads to</p><p>where I is identity matrix. Indeed, as long as the number of points and the percentage of missing entries is small, we use the above formulation. However, when the number of points and/or the percentage of missing entries increases, the size of D &gt; D will be large and computation of the inverse, which is cubic in the size of the matrix, will be computationally prohibitive. Thus, we propose to solve A using the Linearized ADM technique, which also enjoys convergence to optimal solution (Yang and Yuan 2013). To do so, we approximate the term involving A with its linearized form as</p><p>where &#8999; 1 &gt; 0 is the proximal parameter. Hence, we can compute the solution of A as</p><p>-To solve for Q, while fixing other unknowns, we need to minimize the Lagrangian with respect to the terms involving Q, i.e., need to solve the following subproblem</p><p>While we can solve for Q in closed-form, the solution requires to compute the inverse of (F r &#8998;F c ) &gt; (F r &#8998;F c ), where &#8998; denotes the the kronecker product. Since this computation is expensive, we use a linearization of ( <ref type="formula">15</ref>) and solve the following subproblem</p><p>where &#8999; 2 &gt; 0 is a proximal parameter, and g k is the gradient of</p><p>As a result, solving (16), we obtain the following closedform solution for Q k+1 ,</p><p>Algorithm 1 Input: Incomplete data matrix &#562; , side information matrices F r , F c and set of indices of observed entries &#8486;.</p><p>2 , &#915; 0 3 as zero matrices. 2: Update A k+1 using the equation ( <ref type="formula">13</ref>) or ( <ref type="formula">14</ref>). 3: Update Q k+1 using the equations ( <ref type="formula">18</ref>). 4: Update Y k+1 using the equation ( <ref type="formula">19</ref>). 5: Update Z k+1 using ( <ref type="formula">20</ref>) and ( <ref type="formula">21</ref>). 6: Update V k+1 using ( <ref type="formula">20</ref>) and ( <ref type="formula">21</ref>). 7: Update the multipliers &#915; k+1 1 , &#915; k+1 2 , &#915; k+1 3 using ( <ref type="formula">22</ref>). 8: Set k = k +1. While not converged, go to step 2. 9: return Y , A, Q.</p><p>-To solve for Y , we minimize the Lagrangian with respect to Y while fixing other optimization matrices. The solution of the corresponding least square problem leads to</p><p>(19) -At iteration k +1, minimizing the augmented Lagrangian with respect to Z, while fixing other matrices, leads to the soft thresholding operation,</p><p>for the entires of Z (c) , where denotes the Hadamard product. On the other hand, the solution for other entries of Z is given by</p><p>-At iteration k +1, minimizing the augmented Lagrangian with respect to V , while fixing other matrices, leads to</p><p>where svt(M ,t) is the singular value thresholding operation <ref type="bibr">(Cai, Cand&#232;s, and Shen 2010)</ref>.</p><p>-Finally we update the Lagrange multiplier matrices &#915; 1 , &#915; 2 , &#915; 3 by a coordinate ascent method,</p><p>Algorithm 1 shows the steps of our framework.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Experiments</head><p>In this section, we evaluate the performance of our proposed algorithm for high-rank matrix completion against the existing methods on both synthetic and real data and in both low-rank and high-rank settings. We compare our method with Maxide <ref type="bibr">(Xu, Jin, and Zhou 2013)</ref>, IMC (Natarajan and Dhillon 2014), dirtyIMC <ref type="bibr">(Chiang, Hsieh, and Dhillon 2015)</ref> and SIM <ref type="bibr">(Lu et al. 2016</ref>).<ref type="foot">foot_0</ref> All the methods address the problem of low-rank matrix completion with side information. In contrast, our framework addresses the more challenging and general problem of high-rank matrix completion with side information. Given a ground-truth data matrix, Y &#8676; , we drop the values of fraction of the entries uniformly at random and change from 0.1 to 0.9. Given the recovered completed data, Y , we compute the relative matrix completion error as</p><p>In the experiments, for our proposed method, we set = 10, &#8674; =2&#8677; 10 2 , &#181; 1 = &#181; 2 = 10 5 , = 10 2 , &#8999; 1 = 10 5 , &#8999; 2 = 10 2 . Experimentally, we observed robust performance with respect to the change of these parameters.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Synthetic Experiments</head><p>We first evaluate different methods on synthetic low-rank and high-rank data. We let k r = k c = k and generate F &gt; c so that the columns lie in a union of L low-dimensional subspaces, where the dimension of each subspace is d. To do so, we generate L random d-dimensional bases in R k and generate N g random data points in each subspace, forming matrices {B i 2 R k&#8677;Ng } L i=1 . We then form Table <ref type="table">1</ref> shows the average relative matrix completion errors of different methods over 10 random trials. Notice that in both low-rank and high-rank regimes, our method outperforms existing methods across all fractions of missing entries . More specifically, the errors of IMC and SIM are higher than other methods as they rely on the low-rank assumption on the data matrix. Our proposed method and Maxide obtain smaller errors for all , while our method achieves better performance, due to being able to deal with the more general setting of the high-rank data. The performance of DirtyIMC significantly degrades when 0.7 for the low-rank and 0.2 for the high-rank regime. Notice also that the results of all methods degrade in the high-rank case compared to the low-rank regime. However, the performance of our method is less affected, thanks to its ability to handle high-rank data matrices.</p><p>Figure <ref type="figure">1</ref> shows the recovered sparse coefficient matrices C, recovered by our method, for synthetic low-rank (with three subspaces) and high-rank (with ten subspaces)  4.9. We randomly select fraction of labels of Y , as missing entries, and set them to zeros to generate &#562; . We then recover the completed data matrix using different methods and record both the relative matrix completion error (RE) and the transductive label error (TLE). To compute TLE, we take the sign of the entries of the recovered data matrices and then compute the percentage of unobserved labels that are misclassified <ref type="bibr">(Goldberg et al. 2010)</ref>. We report the average of the two errors over 10 random trials. As the results in Figure <ref type="figure">3</ref> illustrates, our proposed method outperforms Maxide, IMC, dirtyIMC and SIM on both types of errors. Notice that the relative completion error (RE) of all algorithms is higher than the transductive label error (TLE). This comes from the fact that while the completed entries might be far from the true values, their sign is compatible with the true label.</p><p>Multi-label learning for music classification. The CAL500 dataset is a collection of 502 "Western popular" songs from 502 unique artists, where each song is has multiple labels from 174 "musically relevant" semantic keywords, corresponding to different categories, such as genre, emotional content and instrumentation <ref type="bibr">(Turnbull et al. 2008</ref>). In addition, each song is represented by a 68dimensional acoustic feature vector extracted from the audio files. In our experiments, the label and feature matrices are Y 2 R 174&#8677;502 and F c 2 R 502&#8677;68 , respectively. Similar to before, we set F r to be the identity matrix. Figure <ref type="figure">4</ref> shows the average multi-label learning and relative completion errors of different methods over 10 random trials. Notice that our proposed method achieves the smallest transductive label errors, in particular, when the fraction of missing entries is smaller than 0.7. Moreover, our method significantly performs better than other algorithms for matrix completion with side information when the missing entries fraction is less than 0.7, thanks to our more general setting of dealing with high-rank data matrices.</p><p>Multi-label learning for image classification. The NUS-WIDE dataset contains more than 269,648 images, where each images is represented by a 128-dimensional feature vector <ref type="bibr">(Spyromitros-Xioufis et al. 2014)</ref>. The images are collected from Flickr, where each image has 81 unique tags (labels) which will be used for our evaluation. In our experiments, we randomly 1,079 images from the dataset (sampling images in the list with steps of 250). Thus the ground truth matrix is Y 2 R 81&#8677;1079 and the feature matrix is F c 2 R 1079&#8677;128 . We set F r to be the identity matrix. In this case, the data matrix Y is high-rank, since the top 75 singular values out of 81 are larger than 1. Figure <ref type="figure">5</ref> shows the average results of different algorithms as a function of the percentage of missing entries of Y , over 10 random trials. Notice that our method achieves the smallest transductive label errors as well as relative completion error across all percentages of missing entries. In particular, with less than 70% missing entries, our method achieves the smallest completion error. Similar to previous cases, the label errors of different methods are smaller than their completion error, as they correctly predict the sign in most cases while the recovered entries can be far from the ground-truth.</p></div>
<div xmlns="http://www.tei-c.org/ns/1.0"><head>Conclusions</head><p>We studied the problem of high-rank matrix completion with side information. We cast the problem as finding a factorization of the data into the product of side information matrices with an unknown interaction matrix, under which each column of the data matrix can be reconstructed using a sparse combination of its other columns. We proposed a lifting framework, where we coupled sparse coefficients and missing values and defined an equivalent optimization, amenable to convex relaxation. We proposed an efficient implementation of our convex framework using a Linearized Alternating Direction Method. Experiments on synthetic and real data demonstrated that our method outperforms existing techniques in dealing with both low and high rank matrices.</p></div><note xmlns="http://www.tei-c.org/ns/1.0" place="foot" n="1" xml:id="foot_0"><p>For Maxide, IMC and SIM, we used the publically available codes. We implemented dirtyIMC, since the code was not available.</p></note>
		</body>
		</text>
</TEI>
