arXiv:1609.03958v1 [stat.ML] 13 Sep 2016

NOISY INDUCTIVE MATRIX COMPLETION UNDER SPARSE FACTOR MODELS
Akshay Soni, Troy Chevalier

Swayambhoo Jain

Yahoo! Research
Sunnyvale, CA, USA
{akshaysoni,troyc}@yahoo-inc.com

Department of ECE
University of Minnesota – Twin Cities
jainx174@umn.edu

ABSTRACT
Inductive Matrix Completion (IMC) is an important class of matrix
completion problems that allows direct inclusion of available features to enhance estimation capabilities. These models have found
applications in personalized recommendation systems, multilabel
learning, dictionary learning, etc. This paper examines a general
class of noisy matrix completion tasks where the underlying matrix
is following an IMC model i.e., it is formed by a mixing matrix
(a priori unknown) sandwiched between two known feature matrices. The mixing matrix here is assumed to be well approximated
by the product of two sparse matrices—referred here to as “sparse
factor models.” We leverage the main theorem of [1] and extend
it to provide theoretical error bounds for the sparsity-regularized
maximum likelihood estimators for the class of problems discussed
in this paper. The main result is general in the sense that it can be
used to derive error bounds for various noise models. In this paper,
we instantiate our main result for the case of Gaussian noise and
provide corresponding error bounds in terms of squared loss.
1. INTRODUCTION
In recent years, matrix completion has been a venue for constant
research—both from theoretical as well as algorithmic front. The
applications include collaborative filtering, multiclass learning, dimensionality reduction etc. In most general terms, the aim of these
problems is to estimate the elements of a matrix X∗ ∈ Rn1 ×n2
from noisy observations collected on only a subset of its locations.
Of course, such estimation problems are ill-posed without further assumptions, since the value of X∗ at the unobserved locations can be
arbitrary. A common approach is to augment the inference method
with the assumption that the underlying matrix to be estimated exhibits some form of intrinsic low-dimensional structure, making, in
some cases, the problem feasible. For example, the assumption of
low-rank on the target matrix has been the main focus of research for
these problems. Even though the rank constrained problem is nonconvex and difficult to analyze, convex relaxations to these problems
have been well studied in noiseless [2], additive uncertainty [3], and
even in settings where observations are nonlinear (e.g., one-bit quantized [4]). However, due to the computational complexity reasons,
the most popular algorithms to solve these problems are variants of
alternating minimization [1]; the low-rank structure is imposed explicitly via bilinear models i.e., X∗ is assumed to be a product of
two factor-matrices as
X∗ = D∗ A∗ ,

(1)

where D∗ ∈ Rn1 ×r , A∗ ∈ Rr×n2 and r ≪ min(n1 , n2 ). Slight
modifications of this formulation also allows for explicit control and

facilitates imposing additional constraints like positivity [5], sparsity
[6], or even tree-sparsity [7] on the factors.
In terms of the well-known user-item recommendation problem [8]: X∗ pertains to the rating matrix, D∗ and A∗ denote the
matrices of user and item latent-factors, respectively. Apart from
the rating information, generally, we also have other user and item
side-features (like age, gender, etc) that can be used to further improve the quality of estimation. These features can be included via
a Bayesian framework [9, 10] or by directly changing the model as
in Inductive Matrix Completion (IMC) [11, 12] where we have the
following model assumption on X∗ :
X∗ = AW∗ B = AP∗ Q∗ B,

(2)

where A ∈ Rn1 ×r1 , B ∈ Rr2 ×n2 are known matrices, for example,
user and item feature matrices, W∗ ∈ Rr1 ×r2 is a mixing matrix
whose low-rank structure is explicitly imposed via a bilinear model
W∗ = P∗ Q∗ , P∗ ∈ Rr1 ×r and Q∗ ∈ Rr×r2 .
The goal of this paper is to provide estimation error bounds for
matrix completion under inductive setting, as in (2), by using the
framework of regularized maximum likelihood estimation [1]. For
generality, we derive these bounds under the assumption that both
P∗ and Q∗ can be sparse, and noise can follow any generic distribution. This kind of sparse-structure arises in recommendation problems where the desire is to have sparse latent vectors due to requirement of low computational and storage complexity [13], and variant
of dictionary learning problems where apart from the coefficient matrix being sparse, dictionary itself is modeled to be sparse [14].
1.1. Related Works
Our inference tasks here essentially entails learning two structured
factors in a bilinear model. With a few notable exceptions (e.g., lowrank matrices and certain non-negative matrices [15, 16]), the nonconvex bilinear models studied in this paper are difficult to analyze.
Several recent efforts in the dictionary learning literature have established theoretical guarantees on identifiability, as well as algorithmic
analyses of a number of optimization approaches [17–20]. The most
closely related to our work are [1, 6, 17], where authors provide a
framework for deriving estimation error bounds for the models of
form (1) under various noise distributions and sparsity structure on
A∗ by using a regularized maximum-likelihood approach based on
the ideas from [21]. The Overall theme of the estimation bounds obtained using this framework is that the error of their estimate, X̂ of
X∗ , decays as the ratio of number of degrees of freedom to estimate
over the number of observations.
The idea of including side features in the factorization models
to improve recommendations is considered using Bayesian formulations in [22] or via directly incorporating these features in a gener-

ative model in IMC [12], Factorization Machines [23]. The statistical performance of IMC has been theoretically analyzed via convex
relaxations based on nuclear-norm in noiseless [12] and noisy settings [24]. From the algorithmic perspective, provable alternatingminimization based approach with bilinear models has been recently
proposed and analyzed [11]. Our results in this paper provide additional insights into these problems under a general setting of noise
and sparsity of the bilinear factors. It is to be noted here that the aim
of all these related works is to accurately estimate the mixing matrix
W∗ ; we provide error bounds for the estimation of X∗ .
Many recent works have used IMC framework for large scale
recommendations [25] or extended IMC to automatically construct
better features [26].
1.2. Specific Contributions
In this paper we provide estimation error guarantees for matrix completion using regularized maximum likelihood estimator under the
model described in (2) for the cases where the factor matrices are
dense (either one or both), or when W∗ is itself sparse. In order to
arrive at these bounds, we extend the fundamental theorem proposed
in [1] to the inductive matrix completion setting studied here. This
extension is detailed in Theorem 2.1. The main utility of this theorem is that it can provide estimation error guarantees for a variety
of noise distributions; for example, Gaussian, Poisson, Laplace, and
even under the extreme quantized setting of 1-bit observations. Here
we instantiate it for the Gaussian noise and obtain corresponding error guarantees.
1.3. Preliminaries
To set the stage for the statement of our main result, we recall
several information-theoretic preliminaries. When p(Y ) and q(Y )
denote the pdf (or pmf) of a real-valued random variable Y , the
Kullback-Leibler divergence (or KL divergence) of q from p is
denoted D(pkq) and given by


p(Y )
D(pkq) = Ep log
q(Y )
where the logarithm is taken to be the natural log. By definition,
D(pkq) is finite only if the support of p is contained in the support of
q. Further, the KL divergence satisfies D(pkq) ≥ 0 and D(pkq) = 0
when p(Y ) = q(Y ). We also use the Hellinger affinity denoted by
A(p, q) and given by
"s
#
#
"s
q(Y )
p(Y )
A(p, q) = Ep
= Eq
p(Y )
q(Y )
It is known that 0 ≤ A(p, q) ≤ 1. When p and q are paramee respecei,j of matrices X and X,
terized by elements Xi,j and X
tively, so that p(Yi,j ) = pXi,j (Yi,j ) and q(Yi,j ) = qXe i,j (Yi,j ), we
P
use the shorthand notation D(pX kqX
e i,j ) and
e) ,
i,j D(pXi,j kqX
Q
A(pX , qX
)
,
,
q
).
Finally,
for
a
matrix
M we
A(p
Xi,j
e
e i,j
i,j
X
denote by kMk0 its number of nonzero elements, and kMkmax the
magnitude of its largest element (in absolute value). Also, (a1 ∨
a2 ) = max(a1 , a2 ).
2. PROBLEM STATEMENT AND RECOVERY RESULT
Our focus here is to estimate a matrix X∗ that admits a model as in
(2) from noisy observations YS = {Yi,j }(i,j)∈S collected at a subset S ⊂ [n1 ]×[n2 ] of its locations. Sampling locations are randomly

chosen in the sense that for an integer m satisfying 4 ≤ m ≤ n1 n2
and γ = m(n1 n2 )−1 , each location is observed independently via
a Bernoulli(γ) model. Going forward, we assume the following
bounds on the participating matrices:
kX∗ kmax ≤ Xmax /2, kP∗ kmax ≤ 1, kQ∗ kmax ≤ Qmax ,
kAkmax ≤ Amax , and kBkmax ≤ Bmax ,
for some positive constants Qmax , Amax , and Bmax .
Given S and YS , we write the joint pdf (or pmf) of the observations as
Y
∗ (Yi,j ),
pXi,j
(3)
pX∗S (YS ) ,
(i,j)∈S

∗ (Yi,j ) denotes the corresponding scalar pdf (or pmf),
where pXi,j
and we use the shorthand X∗S to denote the collection of elements
of X∗ indexed by (i, j) ∈ S. Then our task may be described succinctly as follows: given S and corresponding noisy observations
YS of X∗ distributed according to (3), our goal is to estimate X∗
under the assumption that it admits a model as in (2).
Our approach will be to estimate X∗ via sparsity-penalized maximum likelihood; we consider estimates of the form

b = arg
X

min

X=APQB∈X

{− log pXS (YS ) + λP kPk0 + λQ kQk0 } ,

(4)
where {λP , λQ } > 0 are user-specified regularization parameter,
XS is shorthand for the collection {Xi,j }(i,j)∈S of entries of X indexed by S, and X is an appropriately constructed class of candidate
estimates. To facilitate our analysis here, we take X to be a countable class of estimates constructed as follows: for a specified β ≥ 1,
β
we set Llev = 2⌈log2 (n1 ∨n2 ) ⌉ and construct P to be the set of all
r1 ×r
matrices P ∈ R
whose elements are either 0, or are discretized
to one of Llev uniformly spaced levels in the range [−1, 1] and Q to
be the set of all matrices Q ∈ Rr×r2 whose elements either take the
value zero, or are discretized to one of Llev uniformly-spaced levels
in the range [−Qmax , Qmax ]. Then, we let
X , {X = APQB : P ∈ P, Q ∈ Q, kXkmax ≤ Xmax }. (5)
Our main result establishes error bounds under general noise or
corruption models. We state the result here as a theorem; its proof
appears in Section 3.
Theorem 2.1. Let S, γ, m, β, X , and YS be as defined above and
CD is any constant satisfying
∗ kpX
CD ≥ max max D(pXi,j
i,j ).

X∈X

i,j

Then for any


2CD
λP ≥ 2 1 +
(4 log(r1 ) + β log(n1 ∨ n2 ))
3


2CD
(4 log(r2 ) + β log(n1 ∨ n2 ))
λQ ≥ 2 1 +
3

(6)
(7)

the complexity penalized maximum likelihood estimator (4) satisfies
the (normalized, per-element) error bound


ES,YS −2 log A(pX
8CD log m
b λ , pX∗ )
≤
+
n1 n2
m

D(pX∗ kpX )
+
3 · min
X∈X
n1 n2



4CD (β + 4) log(n1 ∨ n2 )
kPk0 + kQk0
(λP + λQ ) +
.
3
m

Before proceeding to specific case of Gaussian noise, we note a
few salient points about this result. First, as alluded above, our results is general and can be used to analyze the error performance
under a variety of noise models. Specialization to a given noise
model requires us to compute the upper bounds for KL divergences
in terms of problem parameters, and the lower bound of negative log
Hellinger affinities in terms of the required error function. Second,
the above result is kind of an oracle bound, in that it is specified in
terms of a minimum over X ∈ X . We can construct a valid upper
bound by evaluating this for any X ∈ X . We construct a specific
X ∈ X that is close to X∗ , and evaluate the oracle bound for the
constructed point to get a non-trivial upper bound.
Finally, we note that the optimization problem (4) is non-convex,
as often is the case, not only because of ℓ0 penalty, or discretized
space (X ) used for proofs in this paper, but due the fundamental
challenge posed by bilinear models.
2.1. Implications for Gaussian Noise
Below we provide scaling behavior of error bound with problem parameters for Gaussian noise with known variance by instantiating
Theorem 2.1. The joint likelihood of observations can be written as
pX∗S (YS ) =



1
1
∗ 2
,
kY
−
X
k
exp
−
S
S F
2σ 2
(2πσ 2 )|S|/2

(8)

3. PROOFS
3.1. Proof of Theorem 2.1
We utilize the following Lemma from [1] and apply it to our problem.
Lemma 3.1. Let X∗ be an n1 × n2 matrix whose elements we aim
to estimate, and let X be a countable collection of candidate reconstructions X of X∗ , each with corresponding penalty pen(X) ≥ 1,
so
collection of penalties satisfies the summability condition
P that the−pen(X)
≤ 1. Given m, γ, S, YS , and CD as explained
X∈X 2


earlier, we have that for any ξ ≥ 1 + 2C3D ·2 log 2, the complexity
penalized maximum likelihood estimator
b ξ = arg min {− log pX (YS ) + ξ · pen(X)} ,
X
S
X∈X

satisfies the (normalized, per-element) error bound


ES,YS −2 log A(pX
8CD log m
b ξ , pX∗ )
≤
+
n1 n2
m




4CD log 2 pen(X)
D(pX∗ kpX )
3 · min
+ ξ+
,
X∈X
n1 n2
3
m
where, as denoted, the expectation is with respect to the joint distribution of S and YS .

Now, consider any discretized matrix factors P ∈ P and Q ∈
⌈log2 (r1 ·r)⌉
Q, as described in Section 2. For LP
, we encode
loc , 2
P
each nonzero element of P using log 2 Lloc bits to denote its loca
 tion and log2 Llev bits for its amplitude. We can then encode P
√
log(6 m · (r · r1 · r2 ) · Amax Bmax Qmax /Xmax ) with kPk0 nonzero entries by using kPk0 (log2 LP
loc + log 2 Llev )
β = max 1, 1 +
bits. Similarly, we can encode Q using kQk0 (log2 LQ
log(n1 ∨ n2 )
loc +log 2 Llev )
⌈log2 (r2 ·r)⌉
(9)
where LQ
. Now, we let X ′ be set of all such
loc , 2
for describing the number of discretization levels in the elements of
X = APQB, and let the binary code for each X be the concatenaeach factor matrix and regularization parameters (λP , λQ ) equal to
tion of the binary code for P followed by the binary code for Q. It
right hand side of (6). In this setting we have the following result;
follows that we may assign penalties pen(X) to all X ∈ X ′ whose
its proof appears in Section 3.2.
length satisfy
where we have used the shorthand notation kYS − X∗S k2F ,
P
∗ 2
(i,j)∈S (Yi,j − Xi,j ) . To that end, we fix β as

Corollary 2.1. Let β, λP , and λQ be as defined above with CD =
b obtained via (4) satisfies
2X2max /σ 2 . The estimate X
i
h
b 2F
ES,YS kX∗ − Xk

=
(10)
n n
1 2
 ∗


kP k0 + kQ∗ k0
O (σ 2 + X2max )
log(n1 ∨ n2 ) .
m

A few comments are in order regarding these error guarantees.
We may interpret the quantity kP∗ k0 + kQ∗ k0 as the number of
degrees of freedom to be estimated, and in this sense we see that
the error rate of the penalized maximum likelihood estimator exhibits characteristics of the well-known parametric rate (modulo the
logarithmic factor). If P∗ and Q∗ are instead dense, then we get the
familiar error bound that decays as (r1 +r2 )r/m with m. Compared
this with the case where matrix X∗ is just low-rank (as in formal matrix completion tasks), the error rates are of the form (n1 + n2 )r/m
[1]. Clearly, the IMC model has a better error performance if r2 ≪
n2 or even better if the factor matrices are sparse.
The presence of the factor X2max is akin to the incoherence conditions prevalent in the matrix-completion literature. In essence, it
pertains to the spikiness of the underlying matrix we are trying to
estimate [27].

Q
pen(X) = kPk0 (log2 (LP
loc · Llev )) + kQk0 (log 2 (Lloc · Llev )),
(11)
given that A and B are known matrices.
It is easy to see that suchP
codes are (by construction) uniquely
−pen(X)
decodable, so we have that
≤ 1 by the wellX∈X ′ 2
known Kraft-McMillan Inequality [28]. Now let X be any subset
of X ′ . For randomly subsampled and noisy observations YS our
estimates take the form

bξ
X

=

arg

min

X=APQB∈X

{− log pXS (YS ) + ξ · pen(X)} .

Further, using Lemma 3.1 we have


ES,YS −2 log A(pX
8CD log m
b ξ , pX∗ )
≤
+
n1 n2
m

D(pX∗ kpX )
+
3 · min
X∈X
n1 n2




kPk0 + kQk0
4CD log 2
(log2 Lloc + log2 Llev )
,
ξ+
3
m

Q
where log2 Lloc = log 2 LP
loc ∨ log 2 Lloc . Finally, letting
λP

=

λQ

=

ξ · (log2 LP
loc + log 2 Llev )

ξ · (log2 LQ
loc + log 2 Llev )

and using the fact that
log2 LP
loc
log2 LQ
loc

+ log2 Llev

+ log2 Llev
log2 Lloc + log2 Llev

≤

≤
≤

8 log(r1 ) + 2β log(n1 ∨ n2 )

8 log(r2 ) + 2β log(n1 ∨ n2 )
(β + 4) · log(n1 ∨ n2 ) · 2 log 2 (e)

Given the range limits on allowable P and Q and that each range is
quantized to Llev levels, we have that k△P∗ kmax ≤ 1/(Llev − 1)
and k△Q∗ kmax ≤ Qmax /(Llev − 1). Now, we can obtain a bound
on the magnitudes of the elements of X∗q − X∗ that hold uniformly
over all i, j, as follows

kX∗q − X∗ kmax
which follows by our selection of Llev and Lloc and the fact that
r1 < n1 , r2 < n2 ; it follows (after some straightforward simplifica= max |(A(P∗ △Q∗ + △P∗ Q∗ + △P∗ △Q∗ )B)i,j |
i,j
tion) that (λP , λQ ) follow (6), and the estimate (4) satisfies
6
· r · r1 · r2 · Amax Bmax Qmax


≤
,
(12)
ES,YS −2 log A(pX
8CD log m
b , pX∗ )
Llev
≤
+
n1 n2
m

where the inequality follows from a application of triangle inequalD(pX∗ kpX )
ity followed by the bounds on k△P∗ kmax and k△Q∗ kmax and the
3 · min
+
X∈X
n1 n2
entry-wise
bounds on elements of allowable P and Q, and because



Llev ≥ 2. Now, it is straight-forward to show that our choice of β in
kPk0 + kQk0
4CD (β + 4) log(n1 ∨ n2 )
, implies
(λP + λQ ) +
(9)
3
m
as claimed.

Llev ≥

3.2. Proof of Corollary 2.1
∗

Proof. For X as specified and any X ∈ X , using the model (8) we
have
∗
(Xi,j
− Xi,j )2
∗ kpX
D(pXi,j
i,j ) =
2σ 2
for any fixed (i, j) ∈ S. It follows that D(pX∗ kpX ) = kX∗ −
Xk2F /2σ 2 , and using the fact that the amplitudes of entries of X∗
and all X ∈ X are no larger than Xmax , it is clear that we may
choose CD = 2X2max /σ 2 . Further, for any X ∈ X and any fixed
(i, j) ∈ S it is easy to show that in this case
∗ ) =
−2 log A(pXi,j , pXi,j

∗
(Xi,j

2

− Xi,j )
,
4σ 2

so that −2 log A(pX , pX∗ ) = kX∗ − Xk2F /4σ 2 . It follows that
h
i
b 2F
ES,YS kX∗ − Xk


ES,YS −2 log A(pX
.
b , pX∗ ) =
4σ 2

Incorporating this into Theorem 2.1, we obtain that for regularization parameters as in (6) with CD substituted, the sparsity penalized
maximum-likelihood estimate satisfies the per-element mean-square
error bound
i
h
b 2F
ES,YS kX∗ − Xk
64X2max log m
≤
n1 n2
m

kX∗ − Xk2F
+
+ 6 · min
X∈X
n1 n2


16X2max (β + 4) log(n1 ∨ n2 )
2
2σ (λP + λQ ) +
3


kPk0 + kQk0
.
m
We now establish the error bound for the case where P∗ and
Q∗ are sparse with corresponding cardinality kP∗ k0 and kQ∗ k0 .
Consider a candidate reconstruction of the form X∗q = AP∗q Q∗q B,
where the elements of P∗q are the closest discretized surrogates of
the nonzero entries of P∗ , and the entries of and Q∗q are the closest
discretized surrogates of the nonzero entries of Q∗ . Denote P∗q =
P∗ + △P∗ and Q∗q = Q∗ + △Q∗ . Then it is easy to see that
X∗q − X∗ = A(P∗ △Q∗ + △P∗ Q∗ + △P∗ △Q∗ )B.

12 · r · r1 · r2 · Amax Bmax Qmax
,
Xmax

(13)

so each entry of X∗q − X∗ is bounded in magnitude by Xmax /2. It
follows that each element of the candidate X∗q constructed above is
bounded in magnitude by Xmax , so X∗q is indeed a valid element of
the set X .
Further, the approximation error analysis above also implies directly that
kX∗ − X∗q k2F
n1 n2

=

1
n1 n2

X

i∈[n1 ],j∈[n2 ]

(AP∗q Q∗q B − AP∗ Q∗ B)2i,j

≤

36 · (r · r1 · r2 )2 (Amax Bmax Qmax )2
L2lev

≤

X2max
,
m

where the last line follows from the fact that our specific choice of β
in (9) also implies
√
6 m · (r · r1 · r2 ) · Amax Bmax Qmax
Llev ≥
.
(14)
Xmax
Now, evaluating the oracle term at the candidate X∗q = AP∗q Q∗q B,
and using the fact that kP∗q k0 = kP∗ k0 and kQ∗q k0 = kQ∗ k0 , we
have
i
h
b 2F
ES,YS kX∗ − Xk
70X2max log m
≤
+
n1 n2
m
 ∗

kP k0 + kQ∗ k0
48(σ 2 + 2X2max )(β + 4) log(n1 ∨ n2 )
.
m

4. REFERENCES
[1] A. Soni, S. Jain, J. Haupt, and S. Gonella, “Noisy matrix completion under sparse factor models,” IEEE Transactions on
Information Theory, vol. 62, no. 6, pp. 3636–3661, June 2016.
[2] E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” Foundations of Computational Mathematics, vol. 9, no. 6, pp. 717–772, 2009.
[3] R. H. Keshavan, A. Montanari, and S. Oh, “Matrix completion
from noisy entries,” Journal of Machine Learning Research,
vol. 11, pp. 2057–2078, 2010.
[4] M. A. Davenport, Y. Plan, E. van den Berg, and M. Wootters,
“1-bit matrix completion,” Information and Inference, vol. 3,
no. 3, pp. 189–223, 2014.
[5] A. Soni and J. Haupt, “Estimation error guarantees for poisson
denoising with sparse and structured dictionary models,” in
2014 IEEE International Symposium on Information Theory,
June 2014, pp. 2002–2006.
[6] A. Soni, S. Jain, J. Haupt, and S. Gonella, “Error bounds
for maximum likelihood matrix completion under sparse factor
models,” in Signal and Information Processing (GlobalSIP),
2014 IEEE Global Conference on, Dec 2014, pp. 399–403.
[7] A. Soni and J. Haupt, “On the fundamental limits of recovering
tree sparse vectors from noisy linear measurements,” IEEE
Transactions on Information Theory, vol. 60, no. 1, pp. 133–
149, Jan 2014.
[8] Y. Koren, R. Bell, and C. Volinsky, “Matrix factorization techniques for recommender systems,” Computer, vol. 42, no. 8,
pp. 30–37, 2009.

[16] E. Esser, M. Moller, S. Osher, G. Sapiro, and J. Xin, “A convex
model for nonnegative matrix factorization and dimensionality
reduction on physical space,” IEEE Transactions on Image
Processing, vol. 21, no. 7, pp. 3239–3252, 2012.
[17] J. D. Haupt, N. D. Sidiropoulos, and G. B. Giannakis, “Sparse
dictionary learning from 1-bit data,” in 2014 IEEE International Conference on Acoustics, Speech and Signal Processing
(ICASSP), May 2014, pp. 7664–7668.
[18] R. Gribonval and K. Schnass, “Dictionary identification –
Sparse matrix-factorization via l1 minimization,” IEEE Transactions on Information Theory, vol. 56, no. 7, pp. 3523–3539,
2010.
[19] M. Aharon, M. Elad, and A. M. Bruckstein, “On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them,” Linear algebra and its applications, vol. 416, no.
1, pp. 48–67, 2006.
[20] D. A. Spielman, H. Wang, and J. Wright, “Exact recovery
of sparsely-used dictionaries,” in Proceedings of the TwentyThird international joint conference on Artificial Intelligence,
2013, pp. 3087–3090.
[21] A. R. Barron, C. Huang, J. Q. Li, and X. Luo, “The MDL principle, penalized likelihoods, and statistical risk,” Festschrift for
Jorma Rissanen. Tampere University Press, Tampere, Finland,
2008.
[22] Deepak Agarwal and Bee-Chung Chen, “flda: matrix factorization through latent dirichlet allocation,” in Proceedings of
the third ACM international conference on Web search and
data mining. ACM, 2010, pp. 91–100.
[23] Steffen Rendle, “Factorization machines,” in 2010 IEEE International Conference on Data Mining. IEEE, 2010, pp. 995–
1000.

[9] Hao Ma, Haixuan Yang, Michael R Lyu, and Irwin King,
“Sorec: social recommendation using probabilistic matrix factorization,” in Proceedings of the 17th ACM conference on Information and knowledge management. ACM, 2008, pp. 931–
940.

[24] Kai-Yang Chiang, Cho-Jui Hsieh, and Inderjit S Dhillon, “Matrix completion with noisy side information,” in Advances in
Neural Information Processing Systems, 2015, pp. 3447–3455.

[10] Ian Porteous, Arthur U Asuncion, and Max Welling, “Bayesian
matrix factorization with side information and dirichlet process
mixtures.,” in AAAI, 2010.

[25] Donghyuk Shin, Suleyman Cetintas, Kuang-Chih Lee, and Inderjit S Dhillon, “Tumblr blog recommendation with boosted
inductive matrix completion,” in Proceedings of the 24th ACM
International on Conference on Information and Knowledge
Management. ACM, 2015, pp. 203–212.

[11] Prateek Jain and Inderjit S Dhillon, “Provable inductive matrix
completion,” arXiv preprint arXiv:1306.0626, 2013.
[12] Miao Xu, Rong Jin, and Zhi-Hua Zhou, “Speedup matrix completion with side information: Application to multi-label learning,” in Advances in Neural Information Processing Systems,
2013, pp. 2301–2309.
[13] E. Acar, G. Grdeniz, M. A. Rasmussen, D. Rago, L. O. Dragsted, and R. Bro, “Coupled matrix factorization with sparse
factors to identify potential biomarkers in metabolomics,” in
2012 IEEE 12th International Conference on Data Mining
Workshops, Dec 2012, pp. 1–8.
[14] R. Rubinstein, M. Zibulevsky, and M. Elad, “Double sparsity:
Learning sparse dictionaries for sparse signal approximation,”
IEEE Transactions on Signal Processing, vol. 58, no. 3, pp.
1553–1564, March 2010.
[15] Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur
Moitra, “Computing a nonnegative matrix factorization–
provably,” Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pp. 145–162, 2012.

[26] Si Si, Kai-Yang Chiang, Cho-Jui Hsieh, Nikhil Rao, and Inderjit S. Dhillon, “Goal-directed inductive matrix completion,” in
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), aug 2016.
[27] S. Negahban and M. J. Wainwright, “Restricted strong convexity and weighted matrix completion: Optimal bounds with
noise,” The Journal of Machine Learning Research, vol. 13,
no. 1, pp. 1665–1697, 2012.
[28] T. M. Cover and J. A. Thomas, Elements of information theory,
John Wiley & Sons, 2006.

