# Private Matrix Factorization with Public Item Features

Mihaela Curmei Walid Krichene Li Zhang Mukund Sundararajan22footnotemark: 2 UC
Berkeley; Work done while at Google.Google.Microsoft. Work done while at
Google.

###### Abstract

We consider the problem of training private recommendation models with access
to public item features. Training with Differential Privacy (DP) offers strong
privacy guarantees, at the expense of loss in recommendation quality. We show
that incorporating public item features during training can help mitigate this
loss in quality. We propose a general approach based on collective matrix
factorization (CMF), that works by simultaneously factorizing two matrices:
the user feedback matrix (representing sensitive data) and an item feature
matrix that encodes publicly available (non-sensitive) item information.

The method is conceptually simple, easy to tune, and highly scalable. It can
be applied to different types of public item data, including: (1) categorical
item features; (2) item-item similarities learned from public sources; and (3)
publicly available user feedback. Furthermore, these data modalities can be
collectively utilized to fully leverage public data.

Evaluating our method on a standard DP recommendation benchmark, we find that
using public item features significantly narrows the quality gap between
private models and their non-private counterparts. As privacy constraints
become more stringent, models rely more heavily on public side features for
recommendation. This results in a smooth transition from collaborative
filtering to item-based contextual recommendations.

_K_ eywords recommendation system, differential privacy, side features, matrix
factorization

.

##  1 Introduction

Recommender systems trained on private user feedback present the risk of
leaking sensitive information about users’ activity or preferences (Zhang et
al., 2021; Calandrino et al., 2011), and thus, providing formal privacy
protections is increasingly important. Differential privacy (DP) (Dwork et
al., 2014a) has emerged as the de facto standard for formalizing and
quantifying privacy protections. These DP guarantees often come at the expense
of some degradation in model quality, as DP training involves adding noise to
quantities derived from user data (for example, adding noise to the gradients
(Abadi et al., 2016)). Recent progress in private recommendation algorithms
(Jain et al., 2018; Chien et al., 2021; Krichene et al., 2023) has
significantly improved the privacy/utility trade-offs, but there still remains
a large quality gap between private models and their non-private counterparts.

It was recently shown (Krichene et al., 2023; Chien et al., 2021) that these
quality losses are due to degradation in item representation as a result of
the noise added to ensure DP (particularly for tail items, which have fewer
ratings and are more impacted by noise). Making item embeddings robust to the
added noise may be the key to narrowing the quality gap between private and
non-private models. One promising direction is to utilize public item features
to improve item representation while maintaining strict user-privacy
guarantees.

In this work, we investigate methods to utilize such item features to improve
the quality of privacy-preserving recommenders. We take inspiration from the
literature on Collective Matrix Factorization (CMF) (Singh and Gordon, 2008),
which learns shared embeddings from collections of related matrices, rather
than a single matrix. Throughout the paper, we will distinguish between
_private user feedback_ , which is sensitive and needs to be protected, and
_public item features_ , which represent non-sensitive, publicly available
information that does not need privacy protection.

###  1.1 Contributions

  * •

Formulation:

We model both public item features and sensitive user-item feedback as
matrices. Two low-rank factorizations are learned simultaneously. One
factorization approximates the user feedback matrix and the other approximates
the item feature matrix. Importantly, the item representation is shared
between the two factorizations, which enables item embeddings to benefit from
public features. This setup is versatile as it can encode various modalities
of public information. For instance, features can represent public item
metadata. The setup can also encode pairwise item similarity derived from
public data, where the ’features’ correspond to items and represent similarity
scores. Finally, we can encode user feedback, for instance, from users who
choose to make their ratings or reviews publicly available, here, the
’features’ are users and represent the affinity between a user and an item.

  * •

Method: To provide DP guarantees, we propose Differentially Private Collective
Matrix Factorization (DP-CMF), that extends the recently proposed DPALS
algorithm (Chien et al., 2021) to the CMF formulation. DP-CMF works by adding
noise to the sufficient statistics derived from sensitive data, while using
exact statistics derived from public data.

  * •

Evaluation: We evaluate DP-CMF on the same private recommendation benchmark
used in (Jain et al., 2018; Chien et al., 2021; Krichene et al., 2023). We
find that incorporating public item features significantly narrows the quality
gap between private and non-private models, particularly so when privacy
requirements are high. This study offers a promising direction for improving
privacy-utility trade-offs in recommender systems by leveraging public data
sources while preserving user privacy.

###  1.2 Related Work

_Differential privacy in recommender systems._ The importance of privacy in
recommender systems has been recognized for a long time (Narayanan and
Shmatikov, 2008), and some early attempts were made (McSherry and Mironov,
2009; Kapralov and Talwar, 2013) to develop differentially private algorithms
that offer strong protection, but this usually required significant losses in
model quality. Recent work (Jain et al., 2018; Chien et al., 2021; Krichene et
al., 2023) developed new algorithms that narrowed this quality gap, by using
alternating minimization (Chien et al., 2021; Jain et al., 2021), and
developing methods to adaptively allocate privacy budgets (Krichene et al.,
2023). Our proposed algorithm builds on these recent improvements, by
extending the DPALS technique (Chien et al., 2021) to incorporate public item
data. While utilizing public data to improve DP models has been explored in
other domains (as described below), our work is the first to carry out a
systematic study for private recommenders.

_Using side features in recommenders._ User and item side information are
commonly employed to address the ”cold-start” problem for users and items with
limited or no interaction data (Gantner et al., 2010; Saveski and Mantrach,
2014; Kula, 2015; Deldjoo et al., 2019; Cortes, 2018). Furthermore, side
information can tackle fairness concerns and mitigate popularity bias in
recommendations (Shi et al., 2014). Side features can be integrated into MF
models through Collective Matrix Factorization (CMF) (Singh and Gordon, 2008;
Shi et al., 2014; Dong et al., 2017; Liang et al., 2016; Jenatton et al.,
2012), also known as Joint Matrix Factorization (Zhu et al., 2007), which
originated in the Statistical Relational Learning literature (Getoor and
Taskar, 2007). Our work leverages the CMF approach and extends it to private
recommendations. While in recommender systems, both user and item side
information can be useful, in the privacy context, it is more natural to
consider only item side information, as it generally represents non-sensitive
data, while user side information (such as demographic features) is sensitive
and would require privacy protection. Our paper will hence focus on item
features.

_Using public data to improve private models._ Leveraging public information
to enhance privacy/utility trade-offs has been explored in various contexts.
Existing approaches fall in two broad categories. The first is public pre-
training followed by private fine-tuning. Empirically, this approach is
effective in domains with abundant public data, such as natural language
processing (Li et al., 2021; Yu et al., 2021a; Behnia et al., 2022) and vision
(Golatkar et al., 2022; Xu et al., 2022). The second is to directly
incorporate public data into the private learning process. These techniques
are based either on projecting private gradients onto a low-dimensional
subspace estimated from public gradients (Kairouz et al., 2021; Yu et al.,
2021b; Zhou et al., 2021), or utilizing public data to modify the objective
function (Bassily et al., 2020; Amid et al., 2022; Li et al., 2022). For an
extensive review, see (Cummings et al., 2023). These approaches often make the
restrictive assumption that public and private data come from the same
distribution (Kairouz et al., 2021; Amid et al., 2022; Wang and Zhou, 2020;
Zhou et al., 2021) (so that public and private gradients lie on the same
subspace). Our approach can work even if the public data comes from a
different distribution: access to item metadata can be informative about item
similarity, even if this data is of an entirely different nature than user
feedback. Another notable difference is that existing work focuses on
_gradient-based_ methods, while ours is, to the best of our knowledge, the
first to explore the benefits of public data on _second-order_ methods
(Alternating Least Squares).

##  2 Preliminaries

###  2.1 Setup & Notation

Throughout, $\boldsymbol{M}\in\mathbb{R}^{m\times n}$ denotes the user-item
feedback matrix, and $\boldsymbol{S}\in\mathbb{R}^{s\times n}$ the item-
feature matrix, where $m,n,s$ are the number of users, items, and features,
respectively. We denote by $\Omega$ a subset of $[m]\times[n]$ representing
the indices of the observed entries in $\boldsymbol{M}$. We define
$\Omega_{i:}:=\\{j\in[m]:(i,j)\in\Omega\\}$ the set of items rated by user
$i$,and define $\Omega_{:j}:=\\{i\in[n]:(i,j)\in\Omega\\}$ the set of users
that rated item $j$. Further, we denote by $\Omega^{\prime}$ the subset of
$[s]\times[n]$ representing the observed entries of the item-feature matrix.
For instance, $(k,j)\in\Omega^{\prime}$ if item $j$ has corresponding public
feature token $k$ (e.g., $j\equiv$ Titanic, $k\equiv$ director: James
Cameron). The goal of CMF is to learn two low-rank factorizations:
$\boldsymbol{M}_{\Omega}\approx\boldsymbol{U}\boldsymbol{V}^{\top}$ that
approximates the user feedback matrix, and
$\boldsymbol{S}_{\Omega^{\prime}}\approx\boldsymbol{F}\boldsymbol{V}^{\top}$
that approximates the item feature matrix. Where
$\boldsymbol{U}\in\mathbb{R}^{n\times d}$,
$\boldsymbol{V}\in\mathbb{R}^{m\times d}$ and $F\in\mathbb{R}^{s\times d}$ are
$d-$dimension embeddings corresponding to users, items and features,
respectively. The notation $\boldsymbol{M}_{\Omega}$ means that approximate
equality is desired only with respect to the entries $\boldsymbol{M}_{ij}$ for
$(i,j)\in\Omega$.

For a vector $\boldsymbol{v}\in\mathbb{R}^{d}$, $\|\cdot\|$ denotes the usual
Euclidean $\ell^{2}$ norm. For two vectors
$\boldsymbol{u},\boldsymbol{v}\in\mathbb{R}^{d}$,
$\left\langle\boldsymbol{u},\boldsymbol{v}\right\rangle$ and
$\boldsymbol{u}\otimes\boldsymbol{v}$ denote the inner and the outer product,
respectively. By $\Pi_{\text{PSD}}(\cdot)$, we denote the projection operation
on the set of positive semidefinite matrices. By $\|\cdot\|_{frob}$, we denote
the Frobenius norm of a matrix. For a matrix $\boldsymbol{U}$,
$\boldsymbol{u}_{i}$ specifies the $i$-th row. Finally, we use
$\mathcal{N}^{d}$ to denote the standard multivariate normal distribution and
$\mathcal{N}^{d\times d}$ to denote the distribution of symmetric $d\times d$
matrices whose upper triangular entries are i.i.d. standard normal.

###  2.2 Privacy considerations

Following (Jain et al., 2018; Chien et al., 2021; Jain et al., 2021), we adopt
the notion of _user-level_ DP (Dwork et al., 2014a), where the goal is to
protect _all of the ratings_ from a user. Intuitively, the user-level DP
guarantee limits the impact that any user can have on the algorithm’s output.
More formally, let $D=\\{d_{1},d_{2},\ldots d_{n}\\}$ be a set of inputs
corresponding to the $n$ users, and let
$\mathcal{A}:\mathcal{D}^{n}\to\mathcal{Y}$ be a randomized algorithm that
produces an output $y\in\mathcal{Y}$. In our case, $d_{i}$ are the ratings
associated with user $i$ and $y$ is the set of all item embeddings
$\boldsymbol{V}$ and feature embeddings $\boldsymbol{F}$. Denote by $D_{-i}$
the inputs for all users except $i$. Two sets of inputs $D$, $D^{\prime}$ are
said to be _adjacent_ if they differ in at most one user; i.e.
$D=\\{d_{i},D_{-i}\\}$ and $D^{\prime}=\\{d_{i}^{\prime},D_{-i}\\}$.

######  Definition 2.1 (User-level Differential Privacy (Kearns et al.,
2014)).

An algorithm $\mathcal{A}$ satisfies user-level $(\varepsilon,\delta)$-DP if
for all adjacent data sets $D$ and $D^{\prime}$, and any measurable set of
outputs $Y\subset\mathcal{Y}$, the following holds:
$\operatorname{Pr}(\mathcal{A}(D)\in Y)\leq
e^{\varepsilon}\operatorname{Pr}(\mathcal{A}(D^{\prime})\in Y)+\delta.$

Intuitively, $(\varepsilon,\delta)$ are privacy parameters that control the
”indistinguishability” between the outputs of the algorithm when it processes
two datasets that differ in a single user’s data. The smaller the values of
$\varepsilon$ and $\delta$, the stronger the privacy guarantee provided by the
algorithm. The parameter $\delta$ is typically taken to be $\leq 1/n$ ($n$ is
the number of users). The values of $\varepsilon$ depend on the domain,
studies typically report values ranging from $\varepsilon=0.1$ (high privacy
regime) to $\varepsilon=10$.

######  Remark 2.2 (User-level vs. rating-level Differential Privacy).

Some prior techniques (Dwork et al., 2014b; Kapralov and Talwar, 2013) provide
rating-level DP guarantees, meaning that neighboring datasets are allowed to
differ in at most a single rating. In other words, rating-level DP limits risk
of leakage from each individual rating, but this offers a much weaker
protection at the user-level, (since users typically have many ratings, and
the leakage risk compounds with the number of ratings). In contrast, user-
level DP (Kearns et al., 2014; Jain et al., 2018) ensures that a user’s full
set of ratings is protected. This makes user-level DP both more challenging to
accomplish, but also more practically significant and relevant in terms of
privacy protection of a user’s data.

##  3 Differentially Private Collective Matrix Factorization

We now introduce the DP-CMF algorithm for private recommendations with public
item features. We first recall the Alternating Least Squares (ALS) algorithm
for (non-private) CMF, then introduce the necessary modifications to satisfy
user-level DP.

###  3.1 ALS for (non-private) CMF

CMF jointly optimizes the following weighted loss function to find low-rank
approximations of
$\boldsymbol{M}_{\Omega}\approx\boldsymbol{U}\boldsymbol{V}^{\top}$ and
$\boldsymbol{S}_{\Omega^{\prime}}\approx\boldsymbol{F}\boldsymbol{V}^{\top}$.

$\begin{split}\mathcal{L}(\boldsymbol{U},\boldsymbol{V},\boldsymbol{F})=&\sum\limits_{(i,j)\in\Omega}\boldsymbol{W}_{ij}\left(\left\langle\boldsymbol{u}_{i},\boldsymbol{v}_{j}\right\rangle-\boldsymbol{M}_{ij}\right)^{2}+\alpha\sum\limits_{(k,j)\in\Omega^{\prime}}\left(\left\langle\boldsymbol{f}_{k},\boldsymbol{v}_{j}\right\rangle-\boldsymbol{S}_{kj}\right)^{2}+\\\
&+\lambda\left(\|\boldsymbol{U}\|^{2}_{frob}+\|\boldsymbol{V}\|^{2}_{frob}\right)+\lambda^{\prime}\|\boldsymbol{F}\|^{2}_{frob},\end{split}$
(1)

where $\boldsymbol{W}_{ij}$ is the weight associated with the contribution of
user $i$’s rating of item $j$ to the loss function, $\lambda$ is the
regularization weight for user and item embeddings and $\lambda^{\prime}$ is
the regularization weight for feature embeddings. Finally, $\alpha$ is a
hyper-parameter that controls the relative importance of fitting the public
versus private data. A small $\alpha$ means that item embeddings
$\boldsymbol{V}$ will primarily depend on user-item feedback; whereas a large
$\alpha$ means that item embeddings will depend more on the item-feature
matrix. Although the loss is not jointly convex, for fixed item embeddings
$\boldsymbol{V}$, it is a convex quadratic with respect to $(\boldsymbol{U},\
\boldsymbol{F})$ and vice-versa. ALS takes advantage of this fact, and
alternates between updating $(\boldsymbol{U},\boldsymbol{F})$ and updating
$\boldsymbol{V}$, as follows $\forall i\in[n],\forall k\in[s]$ and $\ \forall
j\in[m]$, respectively :

$\displaystyle\boldsymbol{u}_{i}^{t}\xleftarrow{}$
$\displaystyle\arg\min_{u}\sum_{j\in\Omega_{i:}}\left(\boldsymbol{W}_{ij}\left\langle\boldsymbol{u},\boldsymbol{v}_{j}^{t-1}\right\rangle-\boldsymbol{M}_{ij}\right)^{2}+\lambda\|\boldsymbol{u}\|^{2}_{2}=\Bigg{[}\sum_{j\in\Omega_{i:}}\boldsymbol{W}_{ij}\boldsymbol{v}_{j}^{t-1}\otimes\boldsymbol{v}_{j}^{t-1}+\lambda
I\Bigg{]}^{-1}\Bigg{[}\sum_{j\in\Omega_{i}}\boldsymbol{W}_{ij}\boldsymbol{M}_{ij}\boldsymbol{v}_{j}^{t-1}\Bigg{]};$
(2) $\displaystyle\boldsymbol{f}_{k}^{t}\xleftarrow{}$
$\displaystyle\arg\min_{f}\alpha\sum_{j\in\Omega^{\prime}_{k:}}\left(\left\langle\boldsymbol{f},\boldsymbol{v}_{j}^{t-1}\right\rangle-\boldsymbol{S}_{kj}\right)^{2}+\lambda^{\prime}\|\boldsymbol{f}\|^{2}_{2}=\Bigg{[}\sum_{j\in\Omega^{\prime}_{k}}\boldsymbol{v}_{j}^{t-1}\otimes\boldsymbol{v}_{j}^{t-1}+\lambda^{\prime}I\Bigg{]}^{-1}\Bigg{[}\sum_{j\in\Omega^{\prime}_{k:}}\boldsymbol{S}_{kj}\boldsymbol{v}_{j}^{t-1}\Bigg{]};$
(3) $\displaystyle\boldsymbol{v}_{j}^{t}\xleftarrow{}$
$\displaystyle\arg\min_{v}\sum_{i\in\Omega_{:j}}\left(\boldsymbol{W}_{ij}\left\langle\boldsymbol{u}_{i}^{t},\boldsymbol{v}\right\rangle-\boldsymbol{M}_{ij}\right)^{2}+\alpha\sum_{k\in\Omega^{\prime}_{:j}}\left(\left\langle\boldsymbol{f}_{k}^{t},\boldsymbol{v}\right\rangle-\boldsymbol{S}_{kj}\right)^{2}+\lambda\|\boldsymbol{v}\|^{2}_{2}=\left[A^{t}_{j}\right]^{-1}\left[b^{t}_{j}\right];$

where
$A^{t}_{j}:=\Bigg{[}\sum_{i\in\Omega_{:j}}\boldsymbol{W}_{ij}\boldsymbol{u}_{i}^{t}\otimes\boldsymbol{u}^{t}_{i}+\alpha\sum_{k\in\Omega^{\prime}_{:j}}\boldsymbol{f}^{t}_{k}\otimes\boldsymbol{f}_{k}+\lambda
I\Bigg{]}^{-1}$ and
$b^{t}_{j}:=\Bigg{[}\sum_{i\in\Omega_{:j}}\boldsymbol{W}_{ij}\boldsymbol{M}_{ij}\boldsymbol{u}_{i}^{t}+\alpha\sum_{k\in\Omega^{\prime}_{:j}}\boldsymbol{S}_{kj}\boldsymbol{f}^{t}_{k}\Bigg{]}$

The ALS updates for user and feature embeddings (Eqs. (2) and (3)) are
decoupled and can happen simultaneously. In essence, item features (e.g.
genre:comedy) can be treated as “fictitious users”.

######  Remark 3.1 (Implicit feedback and binary features).

When the user feedback is implicit (e.g. clicks, views), or when the public
item features are categorical, we use the implicit ALS formulation (Hu et al.,
2008) that penalizes non-zero predictions outside of the observation sets
$\Omega$ and $\Omega^{\prime}$, by adding terms
$\|\boldsymbol{U}\boldsymbol{V}^{\top}\|_{frob}$ and
$\|\boldsymbol{F}\boldsymbol{V}^{\top}\|_{frob}$ to the optimization objective
in Eq. (1). This results in changes to the update equations that are standard
in the literature.

Input: User-item matrix $\boldsymbol{M}$; feature-item matrix
$\boldsymbol{S}$; feature weight $\alpha$; weight matrix $\boldsymbol{W}$;
initial item embeddings $\boldsymbol{V}^{0}$; number of steps $T$; clipping
parameters $\Gamma_{M}$,$\Gamma_{U}$; regularization parameters
$\lambda$,$\lambda^{\prime}$.

for  _$t=1$ to $T$_ do

1 Broadcast $\boldsymbol{V}^{t-1}$ to all users.

2Each user $i\in[n]$ updates (client-side):

$\boldsymbol{u}_{i}^{t}\xleftarrow{}\left[\sum_{j\in\Omega_{i}}\boldsymbol{v}_{j}^{t-1}\otimes\boldsymbol{v}_{j}^{t-1}+\lambda
I\right]^{-1}\left[\sum_{j\in\Omega_{i}}\boldsymbol{M}_{ij}\boldsymbol{v}_{j}^{t-1}\right]$

3Update feature embeddings (server-side):

$\boldsymbol{f}_{k}^{t}\xleftarrow{}\left[\sum_{j\in\Omega^{\prime}_{k}}\boldsymbol{v}_{j}^{t-1}\otimes\boldsymbol{v}_{j}^{t-1}+\lambda^{\prime}I\right]^{-1}\left[\sum_{j\in\Omega^{\prime}_{k}}\boldsymbol{S}_{kj}\boldsymbol{v}_{j}^{t-1}\right];k\in[s]$

4Update item embeddings (server-side): :

$\boldsymbol{V}^{t}\xleftarrow{}$
DPItemUpdate$(\boldsymbol{M},\boldsymbol{U}^{t},\boldsymbol{F}^{t})$

5return  $\boldsymbol{V}^{T},\boldsymbol{F}^{T}$

Procedure  __DPItemUpdate_ $(\boldsymbol{M},\boldsymbol{U},\boldsymbol{F})$_

6 Clip rating entries:
$\boldsymbol{M}_{ij}=\min(\boldsymbol{M}_{ij},\Gamma_{M});\quad\forall
i,j\Omega$

7Clip user norms:
$\boldsymbol{u}_{i}\xleftarrow{}\max(\|\boldsymbol{u}_{i}\|,\Gamma_{U})\frac{\boldsymbol{u}_{i}}{\|\boldsymbol{u}_{i}\|};\quad\forall
i\in[n]$

for  _$j=1$ to $m$_ do

8 Sample Gaussian noise
$\boldsymbol{G}_{j}\sim\Gamma_{U}^{2}\mathcal{N}^{d\times
d},\quad\boldsymbol{g}_{j}\sim\Gamma_{U}\Gamma_{M}\mathcal{N}^{d}$

9Compute noisy statistics:
$\hat{}\boldsymbol{A}_{j}=\Pi_{\text{PSD}}\left[\sum_{i\in\Omega_{j}}\boldsymbol{W}_{ij}\boldsymbol{u}_{i}\otimes\boldsymbol{u}_{i}+\boldsymbol{G}_{j}+\lambda
I\right]$,
$\hat{b}_{j}=\sum_{i\in\Omega_{j}}\boldsymbol{W}_{ij}\boldsymbol{M}_{ij}\boldsymbol{u}_{i}+\boldsymbol{g}_{j}$

10Compute exact statistics:
$\boldsymbol{A}_{j}^{\prime}=\sum_{k\in\Omega^{\prime}_{j}}\boldsymbol{f}_{k}\otimes\boldsymbol{f}_{k}+\lambda^{\prime}I,\quad\boldsymbol{b}_{j}^{\prime}=\sum_{k\in\Omega^{\prime}_{j}}\boldsymbol{S}_{kj}\boldsymbol{f}_{k}$

11Update item embedding:
$\boldsymbol{v}_{j}\xleftarrow{}[\hat{}\boldsymbol{A}_{j}+\alpha\boldsymbol{A}_{j}^{\prime}]^{-1}[\hat{}\boldsymbol{b}_{j}+\alpha\boldsymbol{b}_{j}^{\prime}]$

12return  $\boldsymbol{V}$

Algorithm 1 Differentially Private CMF with Public Item Features

###  3.2 Differentially Private CMF

To ensure user-level DP, we introduce DP-CMF (see Algorithm 1), which extends
the DPALS procedure (Chien et al., 2021) to CMF with public features. DP-CMF
computes and releases the item and feature embeddings
$(\boldsymbol{V}^{t},\boldsymbol{F}^{t}$) with DP protection on a trusted
centralized platform (server-side). Meanwhile, each user $i$ independently
updates their embedding $\boldsymbol{u}_{i}^{t}$ on their own device (client-
side). As a result, the user embedding update (step 1 of Algorithm 1) is
identical to the non-private update in Eq. (2) with additional assumption that
the update is unweighted (i.e. $W_{ij}=1$). Furthermore, the feature embedding
update (step 1) only depends on $\boldsymbol{S}$ (public data) and
$\boldsymbol{V}^{t-1}$ (which is DP-protected), hence by the DP post-
processing property, it requires no additional noise and can be computed as in
Eq. (3).

On the other hand, the item embedding update (step 1) depends on private data
$\boldsymbol{M},\boldsymbol{U}^{t}$, and must be modified to guarantee DP.
This requires two modifications: the first is to limit the impact of each user
on the item embeddings, this is done by clipping the magnitude of individual
ratings (step 1) clipping the user embedding norm (step 1) and weighting the
ratings of each user with appropriately chosen weights $\boldsymbol{W}$ (step
1). The second is to add noise to the sufficient statistics (steps 1-1) via
the Gaussian mechanism (Vu and Slavkovic, 2009; Foulds et al., 2016; Wang,
2018). Note that the statistics
$\hat{}\boldsymbol{A}_{j},\hat{}\boldsymbol{b}_{j}$ (step 1) depend on
sensitive data and are protected via noise, while the statistics
$\boldsymbol{A}^{\prime}_{j},\boldsymbol{b}^{\prime}_{j}$ (step 1) depend only
on public data and are computed exactly.

######  Remark 3.2.

Step 1 intuitively highlights the potential benefit of using item features:
the item embedding is the solution of a linear system $A\mathbf{x}=b$ with
$A=\hat{}\boldsymbol{A}_{j}+\alpha\boldsymbol{A}^{\prime}_{j}$, and
$b=\hat{}\boldsymbol{b}_{j}+\alpha\boldsymbol{b}_{j}^{\prime}$, where
$\hat{}\boldsymbol{A}_{j},\hat{}\boldsymbol{b}_{j}$ are noisy quantities
derived from user feedback, while
$\boldsymbol{A}_{j}^{\prime},\boldsymbol{b}_{j}^{\prime}$ are derived from
public features and are exact. A larger $\alpha$ makes the solution more
robust to the noise, but favors fitting the item features. When the item
features are informative (e.g., they accurately capture item-item similarity),
this can improve the item representation compared to only using noisy user
feedback $(\alpha=0)$.

######  Remark 3.3 (Computational cost of DP-CMF).

One step of DPALS(Chien et al., 2021) consists of forming the sufficient
statistics (a cost of $O(|\Omega|d^{2})$) then solving $m+n$ linear systems (a
cost of $O((m+n)d^{3})$. In DP-CMF (Algorithm 1), the sufficient statistics
computation cost increases to $O((|\Omega|+|\Omega^{\prime}|d^{2})$, and the
linear system cost increases to $O((m+n+s)d^{3})$. Hence, the added cost of
using public features remains reasonable if $|\Omega^{\prime}|$ is comparable
in size to $|\Omega|$, and the total number of features $s$ is smaller or
comparable to $m+n$.

######  Remark 3.4 (Threat model).

Observe that in this model, the recommendation platform broadcasts the item
embeddings $\boldsymbol{V}$ and the feature embeddings $\boldsymbol{F}$. The
user embeddings $\boldsymbol{U}$ are never published. Rather, each user $i$
can compute her own embedding $\boldsymbol{u}_{i}$ (by solving a least-squares
problem involving her own ratings along with the published item embeddings
$\boldsymbol{V}$, see Eq. (1)), then use it to generate recommendations by
computing scores $\boldsymbol{u}_{i}^{\top}\boldsymbol{V}$. This captures a
very strong notion of privacy, as it protects user $i$ even against potential
collusion of the remaining $n-1$ users (i.e. an adversary with access to
$\boldsymbol{V},\boldsymbol{F}$ and $D_{-i}$), while allowing the user to take
full advantage of her data to generate recommendations. Importantly, the
platform hosting the recommendation system is a trusted entity (it has access
to the raw user ratings and user embeddings when computing the noisy
sufficient statistics). The goal is to protect against privacy attacks from
malicious users or external agents, not the recommender system itself.
However, if the recommender itself is considered untrusted, these algorithms
(DP-ALS and DP-CMF) can potentially be implemented using secure aggregation
algorithms (Bonawitz et al., 2017), although this comes at an increased
computational cost.

######  Proposition 3.1 (Privacy Guarantee).

For all $\varepsilon>0,\delta\in(0,1)$, if the inputs to Algorithm 1 satisfy
$\sum_{j\in\Omega_{i}}\boldsymbol{W}_{ij}^{2}\leq\frac{\varepsilon^{2}}{4T(\log(1/\delta)+\varepsilon)}\forall
i\in[n]$, then the algorithm is $(\varepsilon,\delta)$ user-level DP.

######  Remark 3.5.

The weights $\boldsymbol{W}$ are used to control a user’s impact on the model.
The simplest way to generate weights that satisfy the condition of the
proposition is to assign a uniform weight to each user. Specifically, given a
desired privacy level $(\varepsilon,\delta)$, let
$\beta=\frac{\varepsilon^{2}}{4T(\log(1/\delta)+\varepsilon)}$, then simply
set $\boldsymbol{W}_{ij}=\sqrt{\beta/|\Omega_{i}|}$ satisfies the inequality
(notice that a user with more ratings, i.e. a larger $|\Omega_{i}|$, will have
lower weights, to limit the solution’s sensitivity to that user’s data). A
more sophisticated method was developed in (Krichene et al., 2023) that adapts
to the item frequencies by putting more weight on infrequent items. We use the
latter in our experiments.

###### Proof.

First, we argue that it suffices to prove the result for $\alpha=0$. Indeed,
by step 1, the statistics
$\boldsymbol{A}_{j}^{\prime},\boldsymbol{b}_{j}^{\prime}$ only depend on the
public feature matrix $\boldsymbol{S}$ and on the feature embeddings
$\boldsymbol{F}^{t}$, which in turn only depends on $\boldsymbol{S}$ and
$\boldsymbol{V}^{t-1}$ (by step 1). Since $\boldsymbol{V}^{t-1}$ is released
with DP protection, there is no additional privacy cost for computing
$\boldsymbol{A}_{j}^{\prime},\boldsymbol{b}_{j}^{\prime}$ (by the post-
processing property of DP (Dwork et al., 2014a, Proposition 2.1)). Therefore
the privacy guarantee of the algorithm with $\alpha=0$ or $\alpha>0$ are
identical. When $\alpha=0$ (no features), the algorithm becomes identical to
DPALS, and the guarantee is proved in (Krichene et al., 2023, Theorem 3.3). ∎

##  4 Empirical Evaluation

We evaluate DP-CMF on a standard DP recommendations benchmark used in (Jain et
al., 2018; Chien et al., 2021; Krichene et al., 2023), based on the MovieLens
datasets (Harper and Konstan, 2015). The benchmark considers a rating
prediction task on the MovieLens 10M (ML10M) dataset, which records over $10$
million ratings ranging from 1 to 5 for $n=69878$ users and $m=10677$ movies.
For the feature-item matrix we consider 3 sources of public data:

_Item metadata._ We construct a categorical feature dataset by cross-
referencing movie IMDb identifiers with data available on Wikidata.org. For
each movie in the ML10M dataset, we collect genre, topic, and cast
information. We construct a binary feature matrix $\boldsymbol{S}$, where each
row corresponds to a feature token (e.g., the first row is labeled as
director:James Cameron, and non-zero entries in this row correspond to movies
directed by James Cameron). The metadata dataset comprises $s=12637$ feature
tokens with an overall feature density of $0.13\%$.

_Item to item similarity scores._ We create an item-to-item similarity dataset
from a non-private recommendation model trained on a variant of the ML20M
dataset, as proposed in (Liang et al., 2018). This dataset, is commonly used
for benchmarking recommender performance on implicit feedback, as the training
data is a binary matrix corresponding to ratings $\geq 4$. We first train a
Matrix Factorization model on the dataset and use the resulting item
embeddings to identify, for each movie, the $k$ most similar movies based on
similarity scores (we experiment with inner product and cosine similarity).
Each row in the feature matrix $\boldsymbol{S}$ corresponds to a movie, with
non-zero values $\boldsymbol{S}_{ij}$ indicating similarity between movies $i$
and $j$. Finally, we consider both actual and binarized scores in the
$\boldsymbol{S}$ feature matrix.

_Public user ratings._ We use the ML20M dataset and select the observations
corresponding to 70152 users that do not overlap with the ML10M users. We
consider this set of user-item feedback as public item side data. More
specifically, each user, whose data is considered public, plays the same
functional role as a feature token. We observe that in this case, the public
data is of the same semantic type as the private data. This setup is closest
to the common assumption in the literature, that private and public data come
from the same or similar distributions. In experiments, we use subsets of
public users of various sizes, ranging from very small values ($s=100$) to the
full available data ($s=70152$). Finally, we consider both raw ratings (from
the original ML20M) as well as binarized ratings.

###  4.1 Experimental procedure

We follow the procedure of (Lee et al., 2016) to partition the ML10M into
train, test and validation datasets. For the privacy parameters, following
(Jain et al., 2018; Chien et al., 2021; Krichene et al., 2023), we consider a
range of $\varepsilon=[1,5,10,20]$ and fix $\delta=10^{-5}$. For each privacy
setting we use the optimal hyper-parameters such as number of ALS iterations
$T$, regularization weight $\lambda$, clipping norm $\Gamma_{U}$ tuned by
(Krichene et al., 2023) for the same task without side features. With these
pre-tuned hyper-parameters, for each $\varepsilon$ and each public data
source, we tune only111Retuning the full set of hyper-parameters may lead to
even stronger performance, but our experiments show that tuning only the two
parameters $\alpha,\lambda^{\prime}$ already achieves quality improvements.
This leads to a simple procedure, where one can first tune the DP-ALS hyper-
parameters, then separately tune the CMF-related parameters
$\alpha,\lambda^{\prime}$. the hyper-parameters corresponding to side
features: the side feature weight $\alpha$ and side feature regularization
$\lambda^{\prime}$. We select hyper-parameters based on performance on
validation set and finally we report performance on test set. Performance is
measured using the Root Mean Squared Error (RMSE) between true and predicted
ratings:
$RMSE(\boldsymbol{U},\boldsymbol{V})=\sqrt{\frac{1}{|\Omega|}\sum_{i,j\in\Omega}(\boldsymbol{M}_{ij}-\left\langle\boldsymbol{u}_{i},\boldsymbol{v}_{j}\right\rangle)^{2}}$.
It is important to note that, although the training loss considers side
feature-item data and the learned embeddings for features play a crucial role
in updating item embeddings, the final performance is measured solely based on
rating data (user feedback). In addition, we report performance metrics sliced
by item popularity to gain a deeper understanding how public item information
impacts the the quality of private models across frequent and infrequent
items.

###  4.2 Results

(a) Privacy-accuracy trade-offs on ML10M

(b) Model performance for $\varepsilon=1$ by item popularity

Figure 1: Impact of public item features on private recommendation accuracy.
Wiki Metadata corresponds to categorical genre, topic and cast features. Item-
Item Similarity considers $k=100$ similar items according to dot product;
ML20M Public Users considers binary observations for ratings $\geq 4$

In Figure 1(a), we compare DP-CMF’s performance to the DPALS algorithm without
side features from (Chien et al., 2021; Krichene et al., 2023) (blue curve),
which is the current state-of-the-art on the ML10M benchmark. We also report
for reference the non-private ALS baseline (dashed line). Incorporating public
item information significantly narrows the existing quality gap between
private and non-private models. The relative improvement depends on the public
data source. Public user rating data (red curve) consistently outperforms
other sources, as expected, since it comes from a closely related
distribution. However, even tangentially related public item data, such as
item metadata from Wikidata, substantially improves model quality.
Furthermore, the different public item data modalities are composable, leading
to compunded accuracy improvements (purple curve). The gap between private and
non-private models is largest for high privacy requirements (low
$\varepsilon$), with side features closing up to 60% of the performance gap.

(a) Feature matrix density across popularity levels.

(b) Share of popular items vs. feature prevalence.

Figure 2: Popularity bias of Wikidata metadata, item-item similarity and ML20M
public users’ data

####  4.2.1 Tail performance

Figure 1(b) shows performance across four popularity buckets for models
trained under privacy parameter $\varepsilon=1$, with each bucket containing
roughly 2500 items. Due to the skewed distribution of ratings, the buckets
hold 86.6%, 9.4%, 3%, and 1% of the all ratings, respectively. Thus, popular
items have a greater impact on overall performance. The performance ordering
of head items (bucket 1) matches the global ordering. However, for tail items
(buckets 2 through 4), the order is reversed, with Wikidata features showing
the most improvement for tail items.

We posit that Wikidata movie metadata outperforms on tail items due to its
less pronounced bias towards popular items. As Fig. 2(a) illustrates, 90% of
feature-item observations from ML20M public users correspond to popular items,
while only 37% of Wikidata feature matrix entries do so. However, feature
density alone doesn’t fully account for this performance difference, as item-
to-item similarity doesn’t perform as well on tail items, despite being
perfectly balanced (by construction, we select the same number of neighbors
for all movies).One hypothesis is that side features are most beneficial for
tail items when they can transfer information from popular items. Fig. 2(b)
supports this, showing that while public users primarily rate popular movies.
Wikidata features, on the other hand, are less frequent, but describe both
popular and tail items. This balance may explain why Wikidata outperforms
other public data sources on tail items. Another notable difference between
the sources of data is illustrated in Fig. 2(b). The figure shows, for each
feature, the fraction of top-bucket movies for that feature (so a fraction of
$r$ means that among all occurrences of that feature, $r$ fraction fall in the
top bucket while the rest fall in other buckets). We can observe that while
public users primarily rate popular movies, Wikidata features are more
balanced across popular and tail items. This may explain why Wikidata
outperforms other data sources on tail items.

####  4.2.2 Performance across public data sources

We find that cast information alone captures most of the performance lift
achieved by Wiki Metadata features (3). The cast information is the most
effective side feature for both head and tail items. This phenomenon is
potentially explained by the fact that cast information is very granular and
plausibly correlates with user preferences.

(a) Privacy-Accuracy Tradeoffs

(b) Sliced RMSE ($\varepsilon=1$)

Figure 3: Performance comparison of DP-CMF using Genre, Topic, and Cast data
from Wikidata Metadata

In Figure 4 we consider variants of pairwise item similarity. We find that the
performance improves with the number of similar items for both cosine and
inner product similarity scoring. Inner product scores generally outperform
cosine similarity scores, in part because they take into account the magnitude
of two vectors, not just their angle. Given that higher magnitudes typically
correspond to more popular items, this leads to popularity bias, reflected in
the comparatively weaker performance of dot product similarities on tail
items.

(a) Privacy-Accuracy Tradeoffs

(b) Sliced RMSE ($\varepsilon=1$)

Figure 4: Comparing DP-CMF performance across varying similarity functions and
numbers of selected similar items

Finally, in Figure 5 we consider public item data derived from public ratings.
Increasing the number of features (in this case, users with public ratings)
significantly enhances model performance. This improvement is more pronounced
when using non-binarized ratings, with the private model’s performance
approaching that of the non-private model even under strict privacy settings.
While the most considerable accuracy gains are achieved with large amounts of
public data ($s=50000$), even modestly sized sources of in-distribution data
($s=1000$) yield performance improvements comparable to the best gains
achieved through Wiki Metadata.

(a) Privacy-Accuracy Tradeoffs

(b) Sliced RMSE ($\varepsilon=1$)

Figure 5: Comparing DP-CMF performance for varying number of ML20M Public
Users (in thousands)

##  5 Discussion

In this work, we introduce DP-CMF, a method aimed at improving the privacy-
accuracy trade-off of private recommendation models. Our technique
incorporates public item feature data into private recommendations that
satisfy $(\varepsilon,\delta)$-DP. This approach is simple to implement, easy
to tune, and highly scalable. DP-CMF allows for the integration of public side
item information, pairwise item similarities, and public rating data. This is
achieved within the same formulation, without requiring any changes in privacy
accounting. Our experimental results demonstrate practical improvements in the
privacy-accuracy trade-off by utilizing public item features.

Identifying public features that align with user interests and enhance
recommendation performance remains a challenge. This task is domain-dependent.
In general, access to high-quality annotations is beneficial, and this may be
harder to obtain in some domains, for instance when content creation is cheap,
and annotations are relatively more expensive. In such cases, another
potential source is learning unsupervised, content-based similarity (Jansen et
al., 2018)

Future work includes comparing DP-CMF with pre-training approaches and
extending our methodology beyond CMF. This could involve exploring other
models that utilize item side features, such as Inductive Matrix Completion
(Gantner et al., 2010; Xu et al., 2013; Chiang et al., 2015; Jain and Dhillon,
2013; Goldberg et al., 2010) which enjoys favorable theoretical guarantees.

## References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’16, page 308–318, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450341394.  doi: 10.1145/2976749.2978318.  URL https://doi.org/10.1145/2976749.2978318.
  * Amid et al. (2022) Ehsan Amid, Arun Ganesh, Rajiv Mathews, Swaroop Ramaswamy, Shuang Song, Thomas Steinke, Vinith M Suriyakumar, Om Thakkar, and Abhradeep Thakurta.  Public data-assisted mirror descent for private model training.  In _International Conference on Machine Learning_ , pages 517–535. PMLR, 2022.
  * Bassily et al. (2020) Raef Bassily, Shay Moran, and Anupama Nandi.  Learning from mixtures of private and public populations.  _Advances in Neural Information Processing Systems_ , 33:2947–2957, 2020.
  * Behnia et al. (2022) Rouzbeh Behnia, Mohamamdreza Ebrahimi, Jason Pacheco, and balaji Padmanabhan.  Ew-tune: A framework for privately fine-tuning large language models with differential privacy, 2022.
  * Bonawitz et al. (2017) Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth.  Practical secure aggregation for privacy-preserving machine learning.  In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’17, page 1175–1191, New York, NY, USA, 2017. Association for Computing Machinery.
  * Calandrino et al. (2011) Joseph A. Calandrino, Ann Kilzer, Arvind Narayanan, Edward W. Felten, and Vitaly Shmatikov.  ”you might also like:” privacy risks of collaborative filtering.  In _2011 IEEE Symposium on Security and Privacy_ , pages 231–246, 2011.  doi: 10.1109/SP.2011.40.
  * Chiang et al. (2015) Kai-Yang Chiang, Cho-Jui Hsieh, and Inderjit S Dhillon.  Matrix completion with noisy side information.  _Advances in neural information processing systems_ , 28, 2015.
  * Chien et al. (2021) Steve Chien, Prateek Jain, Walid Krichene, Steffen Rendle, Shuang Song, Abhradeep Thakurta, and Li Zhang.  Private alternating least squares: Practical private matrix completion with tighter rates.  In _International Conference on Machine Learning_ , pages 1877–1887. PMLR, 2021.
  * Cortes (2018) David Cortes.  Cold-start recommendations in collective matrix factorization.  _arXiv preprint arXiv:1809.00366_ , 2018.
  * Cummings et al. (2023) Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geambasu, Matthew Jagielski, Yangsibo Huang, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, et al.  Challenges towards the next frontier in privacy.  _arXiv preprint arXiv:2304.06929_ , 2023.
  * Deldjoo et al. (2019) Yashar Deldjoo, Maurizio Ferrari Dacrema, Mihai Gabriel Constantin, Hamid Eghbal-Zadeh, Stefano Cereda, Markus Schedl, Bogdan Ionescu, and Paolo Cremonesi.  Movie genome: alleviating new item cold start in movie recommendation.  _User Modeling and User-Adapted Interaction_ , 29(2):291–343, 2019.
  * Dong et al. (2017) Xin Dong, Lei Yu, Zhonghuo Wu, Yuxia Sun, Lingfeng Yuan, and Fangxi Zhang.  A hybrid collaborative filtering model with deep structure for recommender systems.  In _Proceedings of the AAAI Conference on artificial intelligence_ , volume 31, 2017.
  * Dwork et al. (2014a) Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ , 9(3–4):211–407, 2014a.
  * Dwork et al. (2014b) Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang.  Analyze gauss: optimal bounds for privacy-preserving principal component analysis.  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , pages 11–20, 2014b.
  * Foulds et al. (2016) James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri.  On the theory and practice of privacy-preserving bayesian data analysis.  _arXiv preprint arXiv:1603.07294_ , 2016.
  * Gantner et al. (2010) Zeno Gantner, Lucas Drumond, Christoph Freudenthaler, Steffen Rendle, and Lars Schmidt-Thieme.  Learning attribute-to-feature mappings for cold-start recommendations.  In _2010 IEEE International Conference on Data Mining_ , pages 176–185. IEEE, 2010.
  * Getoor and Taskar (2007) Lise Getoor and Ben Taskar.  _Introduction to statistical relational learning_.  MIT press, 2007.
  * Golatkar et al. (2022) Aditya Golatkar, Alessandro Achille, Yu-Xiang Wang, Aaron Roth, Michael Kearns, and Stefano Soatto.  Mixed differential privacy in computer vision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8376–8386, 2022.
  * Goldberg et al. (2010) Andrew Goldberg, Ben Recht, Junming Xu, Robert Nowak, and Jerry Zhu.  Transduction with matrix completion: Three birds with one stone.  _Advances in neural information processing systems_ , 23, 2010.
  * Harper and Konstan (2015) F Maxwell Harper and Joseph A Konstan.  The movielens datasets: History and context.  _Acm transactions on interactive intelligent systems (tiis)_ , 5(4):1–19, 2015.
  * Hu et al. (2008) Yifan Hu, Yehuda Koren, and Chris Volinsky.  Collaborative filtering for implicit feedback datasets.  In _Proceedings of the 2008 Eighth IEEE International Conference on Data Mining_ , ICDM ’08, pages 263–272, 2008.
  * Jain and Dhillon (2013) Prateek Jain and Inderjit S Dhillon.  Provable inductive matrix completion.  _arXiv preprint arXiv:1306.0626_ , 2013.
  * Jain et al. (2018) Prateek Jain, Om Dipakbhai Thakkar, and Abhradeep Thakurta.  Differentially private matrix completion revisited.  In _International Conference on Machine Learning_ , pages 2215–2224. PMLR, 2018.
  * Jain et al. (2021) Prateek Jain, John Rush, Adam Smith, Shuang Song, and Abhradeep Guha Thakurta.  Differentially private model personalization.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 29723–29735. Curran Associates, Inc., 2021.
  * Jansen et al. (2018) Aren Jansen, Manoj Plakal, Ratheet Pandya, Daniel P. W. Ellis, Shawn Hershey, Jiayang Liu, R. Channing Moore, and Rif A. Saurous.  Unsupervised learning of semantic audio representations.  In _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , page 126–130. IEEE Press, 2018.
  * Jenatton et al. (2012) Rodolphe Jenatton, Nicolas Roux, Antoine Bordes, and Guillaume R Obozinski.  A latent factor model for highly multi-relational data.  _Advances in neural information processing systems_ , 25, 2012.
  * Kairouz et al. (2021) Peter Kairouz, Monica Ribero Diaz, Keith Rush, and Abhradeep Thakurta.  (nearly) dimension independent private erm with adagrad rates
via publicly estimated subspaces.  In Mikhail Belkin and Samory Kpotufe,
editors, _Proceedings of Thirty Fourth Conference on Learning Theory_ , volume
134 of _Proceedings of Machine Learning Research_ , pages 2717–2746. PMLR,
15–19 Aug 2021.

  * Kapralov and Talwar (2013) Michael Kapralov and Kunal Talwar.  On differentially private low rank approximation.  In _Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1395–1414. SIAM, 2013.
  * Kearns et al. (2014) Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman.  Mechanism design in large games: Incentives and privacy.  In _Proceedings of the 5th conference on Innovations in theoretical computer science_ , pages 403–410, 2014.
  * Krichene et al. (2023) Walid Krichene, Prateek Jain, Shuang Song, Mukund Sundararajan, Abhradeep Thakurta, and Li Zhang.  Multi-task differential privacy under distribution skew.  _arXiv preprint arXiv:2302.07975_ , 2023.
  * Kula (2015) Maciej Kula.  Metadata embeddings for user and item cold-start recommendations.  _arXiv preprint arXiv:1507.08439_ , 2015.
  * Lee et al. (2016) Joonseok Lee, Seungyeon Kim, Guy Lebanon, Yoram Singer, and Samy Bengio.  Llorma: Local low-rank matrix approximation.  2016\.
  * Li et al. (2022) Tian Li, Manzil Zaheer, Sashank Reddi, and Virginia Smith.  Private adaptive optimization with side information.  In _International Conference on Machine Learning_ , pages 13086–13105. PMLR, 2022.
  * Li et al. (2021) Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto.  Large language models can be strong differentially private learners.  _arXiv preprint arXiv:2110.05679_ , 2021.
  * Liang et al. (2016) Dawen Liang, Jaan Altosaar, Laurent Charlin, and David M Blei.  Factorization meets the item embedding: Regularizing matrix factorization with item co-occurrence.  In _Proceedings of the 10th ACM conference on recommender systems_ , pages 59–66, 2016.
  * Liang et al. (2018) Dawen Liang, Rahul G Krishnan, Matthew D Hoffman, and Tony Jebara.  Variational autoencoders for collaborative filtering.  In _Proceedings of the 2018 world wide web conference_ , pages 689–698, 2018.
  * McSherry and Mironov (2009) Frank McSherry and Ilya Mironov.  Differentially private recommender systems: Building privacy into the netflix prize contenders.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 627–636, 2009.
  * Narayanan and Shmatikov (2008) Arvind Narayanan and Vitaly Shmatikov.  Robust de-anonymization of large sparse datasets.  In _2008 IEEE Symposium on Security and Privacy (sp 2008)_ , pages 111–125, 2008.  doi: 10.1109/SP.2008.33.
  * Saveski and Mantrach (2014) Martin Saveski and Amin Mantrach.  Item cold-start recommendations: learning local collective embeddings.  In _Proceedings of the 8th ACM Conference on Recommender systems_ , pages 89–96, 2014.
  * Shi et al. (2014) Yue Shi, Martha Larson, and Alan Hanjalic.  Collaborative filtering beyond the user-item matrix: A survey of the state of the art and future challenges.  _ACM Computing Surveys (CSUR)_ , 47(1):1–45, 2014.
  * Singh and Gordon (2008) Ajit P Singh and Geoffrey J Gordon.  Relational learning via collective matrix factorization.  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 650–658, 2008.
  * Vu and Slavkovic (2009) Duy Vu and Aleksandra Slavkovic.  Differential privacy for clinical trial data: Preliminary evaluations.  In _2009 IEEE International Conference on Data Mining Workshops_ , pages 138–143. IEEE, 2009.
  * Wang and Zhou (2020) Jun Wang and Zhi-Hua Zhou.  Differentially private learning with small public data.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(04):6219–6226, Apr. 2020.
  * Wang (2018) Yu-Xiang Wang.  Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain.  _arXiv preprint arXiv:1803.02596_ , 2018.
  * Xu et al. (2013) Miao Xu, Rong Jin, and Zhi-Hua Zhou.  Speedup matrix completion with side information: Application to multi-label learning.  _Advances in neural information processing systems_ , 26, 2013.
  * Xu et al. (2022) Zheng Xu, Maxwell Collins, Yuxiao Wang, Liviu Panait, Sewoong Oh, Sean Augenstein, Ting Liu, Florian Schroff, and H. Brendan McMahan.  Learning to generate image embeddings with user-level differential privacy, 2022.
  * Yu et al. (2021a) Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al.  Differentially private fine-tuning of language models.  _arXiv preprint arXiv:2110.06500_ , 2021a.
  * Yu et al. (2021b) Da Yu, Huishuai Zhang, Wei Chen, and Tie-Yan Liu.  Do not let privacy overbill utility: Gradient embedding perturbation for private learning.  _arXiv preprint arXiv:2102.12677_ , 2021b.
  * Zhang et al. (2021) Minxing Zhang, Zhaochun Ren, Zihan Wang, Pengjie Ren, Zhunmin Chen, Pengfei Hu, and Yang Zhang.  Membership inference attacks against recommender systems.  In _Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security_ , CCS ’21, page 864–879, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450384544.
  * Zhou et al. (2021) Yingxue Zhou, Steven Wu, and Arindam Banerjee.  Bypassing the ambient dimension: Private SGD with gradient subspace identification.  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_ , 2021.
  * Zhu et al. (2007) Shenghuo Zhu, Kai Yu, Yun Chi, and Yihong Gong.  Combining content and link for classification using matrix factorization.  In _Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval_ , pages 487–494, 2007.


# Millimeter Wave Channel Estimation for Lens based Hybrid MIMO with Low
Resolution ADCs

Evangelos Vlachos1, Aryan Kaushik2 and Muhammad Z. Shakir3 1Industrial Systems
Institute, Athena Research and Innovation Centre, Greece.
2School of Engineering and Informatics, University of Sussex, United Kingdom.
3School of Computing, Engineering & Physical Sciences, University of the West
of Scotland, United Kingdom.
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The high path loss associated with millimeter wave (mmWave) frequency
communication can be compensated by large scale antenna arrays such as
multiple-input multiple-output (MIMO) systems. The hybrid beamforming
architecture which uses fewer radio frequency chains is implemented to reduce
power consumption and hardware complexity, while still supporting multi-stream
communication. We propose an efficient expectation-maximization (EM)-based
mmWave channel estimator for a lens-based hybrid MIMO system with low
resolution sampling at the receiver. The lens-based beamformer is investigated
to provide increased antenna gain and reduced implementation complexity as the
conventional beam selection network is excluded. Low resolution sampling at
the analog-to-digital converters is implemented for reduced power consumption.
The proposed solution with a robust maximum a posteriori estimator based on
the EM algorithm performs better than the conventional EM approach and minimum
mean square error baselines in medium to high signal-to-noise ratio regions.

###### Index Terms:

mmWave channel estimation, lens-based hybrid MIMO, low resolution ADCs.

##  I Introduction

The next generation standards require increased capacity, high data rates, and
an availability of accurate channel state information at transceivers. The
fifth generation (5G) speeds are being forecast 13 times higher than average
mobile connection by 2023 [1], and 5G subscriptions being 440 million just in
Western Europe by 2027 [2]. The microwave frequency spectrum at sub-6 GHz
frequencies, which we currently use for mobile broadband, is limited to a very
crowded frequency range. This increases the demand for unused but available
spectrum which can be resolved by the use of millimeter wave (mmWave)
frequency spectrum [3]. Large-scale antenna arrays such as multiple-input
multiple-output (MIMO) systems can be incorporated with mmWave communication
to compensate for high path loss at such high frequency.

The high complexity of mmWave MIMO systems can be significantly reduced
through hybrid beamforming (HBF) where the number of radio frequency (RF)
chains and associated analog-to-digital converters (ADCs) and digital-to-
analog converters (DACs) are much less than the number of antennas [4]. Such
systems can also be optimized to achieve high energy efficiency (EE) [5, 6,
7]. More recent applications of low resolution DACs, RF optimization and low
complexity architectures has been into the next generation joint radar-
communication systems [8, 9, 10, 11, 12].

In addition to the phase-shifter-based HBF systems, lens-based beamforming
systems can be implemented as a practical alternative to the conventional
beamforming architectures [13]. These approaches simplify the mmWave MIMO RF
front-end, such as Rotman lens based MIMO system with beam selection and
digital beamforming is discussed in [14]. Reference [15] discusses a broadband
mmWave analog beamforming design based on Rotman lens antenna array, whereas a
practical two-stage Rotman lens analog beamformer is shown in [16]. A lens
antenna array enabled mmWave MIMO communication is discussed in [17] and HBF
is a feasible candidate for mmWave MIMO systems to reduce power consumption
and hardware complexity. Implementing low resolution quantization in mmWave
MIMO systems can reduce power consumption and complexity of such systems [18].

Estimating the channel in mmWave MIMO systems is a challenging problem due to
the distinct channel characteristics of the sparse mmWave channel which
experiences less multipath reflection and refraction than at conventional sub
6-GHz microwave frequencies. Advanced channel estimation approaches have
attracted attention in recent years such as for the case of reconfigurable
intelligent surfaces (RIS) and unmanned aerial vehicles (UAVs)-aided
communication [19, 20]. Reference [21] discuss sparse channel estimation
solutions for mmWave MIMO systems where low resolution ADCs are employed at
the RX. References [23, 24] discuss channel estimation for mmWave MIMO systems
with lens antenna arrays where they exploit mmWave sparsity, and [25]
discusses channel estimation scheme for a three dimensional beamspace channel
model in a lens-based mmWave massive MIMO system. However, channel estimation
for lens enabled mmWave hybrid MIMO systems is not widely studied in existing
literature and low resolution sampling has not been exploited for such
systems.

#### Contributions

This paper proposes an efficient channel estimator for Rotman lens-based
mmWave hybrid MIMO system with low resolution ADCs at the RX. We exploit the
sparsity of the mmWave channel and use the beamspace representation to
formulate sparse signal recovery problem. We then implement a robust maximum a
posteriori (MAP) estimator based on the expectation maximization (EM)
algorithm. The simulation results verify that the proposed robust EM approach
performs better than the conventional EM approach and minimum mean square
error (MMSE) baselines in terms of estimation accuracy, i.e., mean square
error (MSE), and exhibits low computational complexity.

_Notation:_ $\mathbf{A}$, $\mathbf{a}$, and a denote a matrix, a vector, and a
scalar, respectively. The complex conjugate transpose, transpose and complex
conjugate of matrix $\mathbf{A}$ are denoted as $\mathbf{A}^{H}$,
$\mathbf{A}^{T}$ and $\mathbf{A}^{*}$, respectively;
$\textrm{vec}(\mathbf{A})$ denotes the vector of entries of the matrix
$\mathbf{A}$; $\mathbf{I}_{\textrm{N}}$ represents $N\times N$ identity
matrix; $\mathbf{X}\in\mathbb{C}^{A\times B}$ and
$\mathbf{X}\in\mathbb{R}^{A\times B}$ denote an $A\times B$ size $\mathbf{X}$
matrix with complex and real entries, respectively;
$\mathbf{X}\otimes\mathbf{Y}$ denotes the Khatri-Rao product of the
$\mathbf{X}$ and $\mathbf{Y}$ matrices;
$\mathcal{C}\mathcal{N}(\mathbf{a};\mathbf{A})$ denotes a complex Gaussian
vector having mean $\mathbf{a}$ and covariance matrix $\mathbf{A}$; the
expectation of a complex variable is denoted as $\mathcal{E}(\cdot)$;
$[\mathbf{A}]_{k}$ denotes the $k$-th column of matrix $\mathbf{A}$ and
$[\mathbf{A}]_{kl}$ is the matrix entry at the $k$-th row and $l$-th column.

##  II Lens-based MmWave Hybrid MIMO Model

###  II-A MmWave Channel Model

Let us denote the antenna array size at the RX as $M$ and we assume the TX has
only a single antenna. We model the $M\times 1$ uplink channel vector
$\mathbf{h}_{\ell}$ for the $\ell$-th terminal as a double-directional
response, consisting of a finite number of multipath components
$N_{\textrm{P}}$, as follows:

$\mathbf{h}_{\ell}=\frac{1}{\sqrt{N_{\textrm{P}}}}\sum\limits_{p=1}^{N_{\textrm{P}}}\hskip
1.0pt\alpha_{\ell,p}\hskip
2.0pt\Lambda\left(\phi_{\ell,p},\theta_{\ell,p}\right)\mathbf{a}^{H}\left(\phi_{\ell,p},\theta_{\ell,p}\right),$
(1)

where $\alpha_{\ell,p}$, $\Lambda\left(\phi_{\ell,p},\theta_{\ell,p}\right)$
and $\mathbf{a}\left(\phi_{\ell,p},\theta_{\ell,p}\right)$ denote the gain of
the $p$-th multi-path component, the per-antenna element gain and the far-
field steering vector of the uniform rectangular array (URA) [26],
respectively. Also,
$\alpha_{\ell,p}\sim\mathcal{CN}\left(0,\beta_{\ell}\right)$ when
$\beta_{\ell}=\zeta_{\ell}(r_{\textrm{ref}}/r_{\ell})^{\chi}$ captures the
large-scale fading impact within the channel, involving the shadow fading and
geometric attenuation with the distance $r_{\ell}$ from the $\ell$-th user
equipment (UE) to the URA. In particular,
$10\log_{10}(\zeta_{\ell})\sim\mathcal{CN}\left(0,\sigma_{\textrm{sf}}^{2}\right)$,
where $\sigma_{\textrm{sf}}$ is the standard deviation of the shadow fading.
Here $r_{\textrm{ref}}$ is the reference distance from URA, while $\chi$ is
the attenuation exponent.

For mmWave channel estimation, we require the beamspace representation [27,
28] of the channel in (1) which can be expressed as follows:

$\mathbf{H}=\mathbf{D}_{\textrm{R}}\mathbf{Z}\mathbf{D}_{\textrm{T}}^{H},$ (2)

where $\mathbf{Z}\in\mathbb{C}^{N_{\textrm{R}}\times N_{\textrm{T}}}$
represents a sparse channel matrix with a few non-zero entries which are
assumed to follow a Bernoulli-Gaussian distribution, while
$\mathbf{D}_{\textrm{R}}\in\mathbb{C}^{N_{\textrm{R}}\times N_{\textrm{R}}}$
and $\mathbf{D}_{\textrm{T}}\in\mathbb{C}^{N_{\textrm{T}}\times
N_{\textrm{T}}}$ are the discrete Fourier transform (DFT) matrices. By
following the basic matrix multiplication property, i.e.,
$\textrm{vec}(\mathbf{A}\mathbf{X}\mathbf{B})=(\mathbf{B}^{T}\otimes\mathbf{A})\textrm{vec}(\mathbf{X})$,
we can express the following:

$\textrm{vec}(\mathbf{H})=\textrm{vec}(\mathbf{D}_{\textrm{R}}\mathbf{Z}\mathbf{D}_{\textrm{T}}^{H})=(\mathbf{D}_{\textrm{T}}^{*}\otimes\mathbf{D}_{\textrm{R}})\textrm{vec}(\mathbf{Z}),$
(3)

where $\mathbf{z}=\textrm{vec}(\mathbf{Z})$, i.e., the mmWave channel vector
to be estimated in Section III below.

###  II-B Quantization Model

We consider the outputs of the two dimensional Rotman lens-based beamformer to
be connected to $L$ parallel RF chains which represent the received complex
signal vector $\mathbf{y}\in\mathbb{C}^{L\times 1}$. This signal passes
through $L$ ADCs with low-resolution quantization, i.e., $b\in\\{3,4,5\\}$
bits for each real or imaginary component. Hence,

$\mathbf{r}=\mathcal{Q}\big{(}\mathtt{Re}(\mathbf{y})\big{)}+j\mathcal{Q}\big{(}\mathtt{Im}(\mathbf{y})\big{)}$
(4)

where $\mathcal{Q}(\cdot)$ represents a uniform symmetric mid-riser type
quantizer which is applied independently at each component of the input
vector. Specifically, for the scalar input $x$ it is defined as:

$\mathcal{Q}(x)=\textrm{sign}(x)\left[\min\left(\left\lceil\frac{|x|}{\delta}\right\rceil,2^{b-1}\right)-\frac{1}{2}\right]\delta$
(5)

where $\delta\triangleq\big{(}\mathcal{E}(|x|^{2})\big{)}^{1/2}\gamma$ and
$\gamma$ is the quantization stepsize. We assume that the average power
$\mathcal{E}(|x|^{2})$ is known, measured by an automatic gain control unit,
while the stepsize $\gamma$ is chosen optimally so as to minimize the
quantization error assuming a Gaussian input signal.

###  II-C Lens-based Hybrid MIMO System Model

We consider a base station (BS) equipped with an URA followed by a Rotman
lens-based hybrid MIMO beamformer. In a traditional MIMO system at sub 6-GHz
microwave frequencies, each antenna element is connected to one RF chain which
is followed by the digital baseband processing unit. In mmWave MIMO systems,
we make use of HBF where there are fewer RF chains than the number of
antennas. We implement the HBF architecture where we can use a smaller number
of RF chains with a larger number of antenna elements, e.g., 15 (3 Rotman
lenses with access points $N_{\textrm{ap}}=5$).

The $L\times 1$ down-converted signal $\mathbf{y}\in\mathbb{C}^{L\times 1}$
can be written as

$\mathbf{y}=\rho^{1/2}\mathbf{F}_{\textrm{RF}}\mathbf{H}\mathbf{s}+\mathbf{n},$
(6)

where $\mathbf{s}\in\mathbb{C}^{L\times 1}$ is the $L\times 1$ transmitted
symbol vector from all terminals,
$\mathbf{H}\in\mathbb{C}^{N_{\textrm{R}}\times L}$ is the mmWave channel
matrix, $\mathbf{F}_{\textrm{RF}}\in\mathbb{C}^{L\times N_{\textrm{R}}}$ is
the lens-based beamformer matrix and $\mathbf{n}\in\mathbb{C}^{L\times 1}$ is
the additive complex Gaussian noise vector with
$\mathbf{n}\sim\mathcal{CN}(\mathbf{0},\sigma_{\textrm{n}}^{2}\mathbf{I}_{\textrm{L}})$.
We assume that the beamformer is capable of creating $M$ fixed analog beams
along azimuth and elevation sectors as
$(\phi_{1},\theta_{1}),\ldots,(\phi_{M},\theta_{M})$. The net functionality of
the lens-based beamformer when considering a perfect focusing capability is
described by the $L\times{}M$ matrix:

$\mathbf{F}_{\textrm{RF}}=\left[\hskip
1.0pt\mathbf{a}^{H}\left(\phi_{1},\theta_{1}\right)\hskip
3.0pt\mathbf{a}^{H}\left(\phi_{2},\theta_{2}\right)\hskip 3.0pt\dots\hskip
3.0pt\mathbf{a}^{H}\left(\phi_{M},\theta_{M}\right)\hskip
1.0pt\right]^{T}.\vspace{0pt}$ (7)

Furthermore, (6) can be re-written, by following the property of
$\textrm{vec}(\mathbf{A}\mathbf{X}\mathbf{B})=(\mathbf{B}^{T}\otimes\mathbf{A})\textrm{vec}(\mathbf{X})$,
as following:

$\mathbf{y}=\rho^{1/2}\mathbf{F}_{\textrm{RF}}(\mathbf{s}^{T}\otimes\mathbf{I})\textrm{vec}(\mathbf{H})+\mathbf{n}.$
(8)

Following (3), we can express the signal $\mathbf{y}$ in terms of the channel
vector $\mathbf{z}$ as follows:

$\displaystyle\mathbf{y}=$
$\displaystyle\rho^{1/2}\mathbf{F}_{\textrm{RF}}(\mathbf{s}^{T}\otimes\mathbf{I})(\mathbf{D}_{\textrm{T}}^{*}\otimes\mathbf{D}_{\textrm{R}})\textrm{vec}(\mathbf{Z})+\mathbf{n}$
$\displaystyle=$
$\displaystyle\rho^{1/2}\mathbf{F}_{\textrm{RF}}(\mathbf{s}^{T}\otimes\mathbf{I})(\mathbf{D}_{\textrm{T}}^{*}\otimes\mathbf{D}_{\textrm{R}})\mathbf{z}+\mathbf{n}.$
(9)

##  III Proposed Channel Estimator

###  III-A Problem Formulation

We consider a two-stage stacked Rotman lens-based beamformer, which eliminates
the requirement of a switching matrix [16], which directly reduces the
complexity of a mmWave hybrid MIMO architecture. However, closely spaced
antenna elements are subject to mutual coupling that has a negative impact on
per antenna element efficiency and there are inherent losses associated with
the Rotman lens [29]. We consider realistic beam patterns for the Rotman lens
system in an anechoic chamber. Thus, we model these imperfections of the
antenna and the beamformer according to

$\mathbf{F}_{\textrm{RF}}=\mathbf{E}_{m}\circ\mathbf{F}_{\textrm{RF}}^{o}+\mathbf{E}_{a}$
(10)

where $\mathbf{E}_{m},\mathbf{E}_{a}\in\mathbb{C}^{L\times N_{\textrm{T}}}$
represent the beamformer imperfections and $\mathbf{F}_{\textrm{RF}}^{o}$ is
the ideal beamformer matrix. The $(r,s)$-th element of the multiplicative
noise matrix is given by $[\mathbf{E}_{m}]_{r,s}=e^{j\delta_{r,s}}$ with
$\delta_{r,s}\sim\mathcal{CN}(0,\epsilon_{m}^{2})$, where $\epsilon_{m}$
controls the level of spillover loss. For the additive noise matrix we have
that its entries are drawn independently as white Gaussian random variables,
i.e., $[\mathbf{E}_{a}]_{r,s}\sim\mathcal{CN}(0,\epsilon_{a}^{2})$.

Then, the received signal $\mathbf{r}$, measured at the outputs of the ADCs is
expressed as

$\displaystyle\mathbf{r}=\mathcal{Q}(\mathbf{y})$
$\displaystyle=\mathcal{Q}(\mathbf{F}_{\textrm{RF}}\mathbf{H}\mathbf{s}+\mathbf{n})$
(11)
$\displaystyle=\mathcal{Q}((\mathbf{E}_{m}\circ\mathbf{F}_{\textrm{RF}}^{o})\mathbf{H}\mathbf{s}+\mathbf{E}_{a}\mathbf{H}\mathbf{s}+\mathbf{n})$
(12)
$\displaystyle=\mathcal{Q}(\underbrace{(\mathbf{s}^{T}\otimes(\mathbf{E}_{m}\circ\mathbf{F}_{\textrm{RF}}^{o}))(\mathbf{D}_{\textrm{T}}^{*}\otimes\mathbf{D}_{\textrm{R}})}_{\mathbf{\Psi}}\underbrace{\textrm{vec}(\mathbf{Z})}_{\mathbf{z}}+\mathbf{d}+\mathbf{n}),$
(13)

where $\mathbf{d}\in\mathbb{C}^{N_{\textrm{R}}\times 1}$ represents the
beamforming noise, which is unknown in general since we have no knowledge of
the noise matrix $\mathbf{E}_{a}$.

The unknown vector $\mathbf{d}$ is also a Gaussian random variable with
covariance matrix given by:

$\boldsymbol{\Sigma}_{\textrm{d}}^{2}=\mathcal{E}\\{\mathbf{H}^{H}\mathbf{E}_{a}^{H}\mathbf{E}_{a}\mathbf{H}\\}=\epsilon_{a}^{2}\mathcal{E}\\{\mathbf{H}^{H}\mathbf{H}\\}=\epsilon_{a}^{2}\mathcal{E}\\{\mathbf{Z}^{H}\mathbf{Z}\\},$
(14)

given that $\mathcal{E}\\{\|\mathbf{s}\|^{2}\\}=1$. Given that the channel has
the line-of-sight (LoS) path, and very few weak non-LoS paths, the covariance
matrix of the channel has strong diagonal structure, and thus it can be
approximated by:

$\mathcal{E}\\{\mathbf{Z}^{H}\mathbf{Z}\\}\approx\sigma_{\alpha}^{2}\mathbf{I},$
(15)

where $\sigma_{a}lpha$ is the channel gain of the LoS path. Therefore, the
covariance matrix of the noise vector $\mathbf{d}$ can be approximated by:

$\boldsymbol{\Sigma}^{2}_{\textrm{d}}\approx\sigma_{\alpha}^{2}\epsilon_{a}^{2}\mathbf{I}.$
(16)

The output can be expressed as the signal plus two noise vectors, i.e.,
$(\mathbf{d}+\mathbf{n})$. Finally the system model can be expressed as

$\displaystyle\mathbf{r}=\mathbf{\Psi}\mathbf{z}+(\mathbf{d}+\mathbf{n}),$
(17)

where the unknown channel $\mathbf{z}$ can be estimated using an efficient
technique such as that shown in the following subsection.

It is well known that the quantization function $\mathcal{Q}(\cdot)$ is a non-
linear function and therefore difficult to analyze directly. This makes the
simple linear estimators such as the linear miminum mean square (LMMSE)
inappropriate, resulting in high estimation errors. However, working on the
statistical properties of the quantized signal allows strictly linear
operations to be performed [30]. To this end, we focus on the MAP estimator,
which can be expressed as:

$\mathbf{\hat{h}}=\textrm{arg}\max_{\mathbf{z},\mathbf{d}}p(\mathbf{r},\mathbf{y},\mathbf{d},\mathbf{z}),$
(18)

with $p(\mathbf{r},\mathbf{y},\mathbf{d},\mathbf{z})$ as the joint probability
distribution function (PDF) of the quantized output, the received signal, the
unknown noise and the unknown channel vector.

###  III-B Alternating Minimization

In this subsection, we propose a MAP estimator to obtain the unknown channel
vector $\mathbf{z}$. The proposed technique is based on the EM algorithm [31]
which approximates the MAP solution. Specifically, EM is an iterative method
that tries to find the maximum likelihood estimator of a parameter
$\mathbf{z}$ of a parametric probability distribution
$\mathbf{p(\mathbf{r}|\mathbf{z}})$. The quantities $\mathbf{y}$ and
$\mathbf{d}$ are considered as unknown and they are computed by the EM
approach [32].

######  Proposition 1.

Given the noise covariance matrix $\mathbf{R}_{\textrm{d}}$, the following
iterative EM algorithm converges to the optimum solution. Specifically, at the
$(m+1)$-th iteration the following steps are performed:

  * •

E-step
Compute the vector $\mathbf{b}^{(m+1)}\in\mathbb{R}^{2L\times 1}$ with

$[\mathbf{b}^{(m+1)}]_{i}=-\frac{\sigma_{\textrm{n}}}{\sqrt{2\pi}}\frac{\xi(l_{i})-\xi(u_{i})}{\Xi(l_{i})-\Xi(u_{i})}$
(19)

where $l_{i},u_{i}$ are the lower/upper bounds of the quantizer for
$[\mathbf{r}]_{i}$ respectively;

$\xi(a)\triangleq
e^{-\frac{(a-[\mathbf{\Psi}\mathbf{z}^{(m)}]_{i}-[\mathbf{d}]_{i})^{2}}{2\sigma^{2}}},$
$\Xi(a)\triangleq\mathrm{erf}(\frac{-a+[\mathbf{\Psi}\mathbf{z}^{(m)}]_{i}+[\mathbf{d}]_{i}}{\sqrt{2}\sigma_{\textrm{n}}}),$

where $\mathrm{erf}(\cdot)$ is the error function.

  * •

M-step

    * –

Estimate the channel vector $\mathbf{z}^{(m+1)}\in\mathbb{R}^{2L\times 1}$ by
estimating the linear system of equations:

$\mathbf{A}\mathbf{z}^{(m+1)}=\mathbf{\Psi}^{T}\mathbf{c},$ (20)

where

$\mathbf{A}\triangleq\mathbf{\Psi}^{T}\mathbf{\Psi}+\sigma_{\textrm{n}}^{2}\mathbf{I}_{\textrm{L}},$
$\mathbf{c}\triangleq\mathbf{\Psi}\mathbf{z}^{(m)}+\mathbf{b}^{(m+1)}+\mathbf{d}^{(m)}$

    * –

Obtain the update of the noise vector:

$\mathbf{d}^{(m+1)}=\mathbf{R}_{\textrm{d}}\mathbf{\Psi}\mathbf{z}^{(m+1)}$
(21)

#### Proof

The joint PDF can be written as:
$p(\mathbf{r},\mathbf{y},\mathbf{d},\mathbf{z})=p(\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z})p(\mathbf{r}|\mathbf{y})p(\mathbf{z})=p(\mathbf{y}|\mathbf{d},\mathbf{r},\mathbf{z})p(\mathbf{r}|\mathbf{y})p(\mathbf{d})p(\mathbf{z})$.
Hence, taking the expectation over the unknown variables we have:

$\displaystyle\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\ln
p(\mathbf{r},\mathbf{y},\mathbf{d},\mathbf{z})\right\\}=\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\ln
p(\mathbf{y},\mathbf{r}|\mathbf{d},\mathbf{z})\right\\}$ $\displaystyle\hskip
30.00005pt+\ln
p(\mathbf{r}|\mathbf{y})+\mathcal{E}_{\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\ln
p(\mathbf{d})\right\\}+\ln p(\mathbf{z})$ (22)

The first term can be written as:
$\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\ln
p(\mathbf{y}|\mathbf{r},\mathbf{d},\mathbf{z})\right\\}=-\frac{1}{2\sigma_{\textrm{n}}^{2}}\mathcal{E}\left\\{\|\mathbf{y}-\mathbf{\Psi}\mathbf{z}-\mathbf{d}\|_{2}^{2}\right\\}+\kappa_{1}$,
with $\kappa_{1}$ a constant term. The expectation term is further expanded
as:

$\displaystyle\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\|\mathbf{y}-\mathbf{\Psi}\mathbf{z}-\mathbf{d}\|_{2}^{2}\right\\}=\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\|\mathbf{y}-\mathbf{d}\|_{2}^{2}\right\\}$
$\displaystyle\hskip
40.00006pt-2\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{(\mathbf{y}-\mathbf{d})^{T}\mathbf{\Psi}\mathbf{z}\right\\}+\|\mathbf{\Psi}\mathbf{z}\|_{2}^{2}.$
(23)

Keeping only the terms that depend on $\mathbf{z}$ and $\mathbf{d}$ we define
the function:

$\displaystyle\mathcal{G}$
$\displaystyle\triangleq-\frac{1}{2\sigma_{\textrm{n}}^{2}}\left(-2\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{(\mathbf{y}-\mathbf{d})^{T}\mathbf{\Psi}\mathbf{z}\right\\}+\|\mathbf{\Psi}\mathbf{z}\|_{2}^{2}\right.$
$\displaystyle\left.+\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{-2\mathbf{y}^{T}\mathbf{d}+\|\mathbf{d}\|_{2}^{2}\right\\}\right)+\ln
p(\mathbf{z})$ (24)
$\displaystyle=\frac{1}{2\sigma_{\textrm{n}}^{2}}\left(2\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\mathbf{y}\right\\}^{T}\mathbf{\Psi}\mathbf{z}+2\mathbf{d}^{T}\mathbf{\Psi}\mathbf{z}-\|\mathbf{\Psi}\mathbf{z}\|_{2}^{2}\right.$
$\displaystyle\left.-\|\mathbf{d}\|_{2}^{2}+2\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{\mathbf{y}\right\\}^{T}\mathbf{d}\right)-\frac{1}{2\sigma_{\textrm{s}}^{2}}\|\mathbf{z}\|_{2}^{2}$
(25)

where (III-B) represents the mean of the truncated Gaussian random variable.
Hence,

$\mathcal{E}_{\mathbf{y},\mathbf{d}|\mathbf{r},\mathbf{z}^{(m)}}\left\\{[\mathbf{y}]_{i}\right\\}=[\mathbf{\Psi}\mathbf{z}^{(m)}]_{i}+\sigma_{n}\frac{\xi(r_{i}^{\textrm{lo}})-\xi(r_{i}^{\textrm{up}})}{\Xi(r_{i}^{\textrm{up}})-\Xi(r_{i}^{\textrm{lo}})}.$
(26)

Taking the derivative of $\mathcal{G}$ over $\mathbf{z}$ and setting it equal
to zero, we have:

$\displaystyle\frac{\partial\mathcal{G}}{\partial\mathbf{z}}=0\Rightarrow
2\mathbf{\Psi}^{T}\mathbf{c}-2(\mathbf{\Psi}^{T}\mathbf{\Psi}+\frac{\sigma_{\textrm{n}}^{2}}{\sigma_{\textrm{s}}^{2}})\mathbf{z}=0$
(27)

where
$\mathbf{c}\triangleq[\mathbf{\Psi}\mathbf{z}^{(m)}]_{i}+\sigma_{\textrm{n}}\frac{\xi(r_{i}^{\textrm{lo}})-\xi(r_{i}^{\textrm{up}})}{\Xi(r_{i}^{\textrm{up}})-\Xi(r_{i}^{\textrm{lo}})}-\mathbf{d}$.

Taking the derivative of $\mathcal{G}$ over $\mathbf{d}$ and setting it equal
to zero, we have:

$\displaystyle\frac{\partial\mathcal{G}}{\partial\mathbf{d}}=0\Rightarrow\mathbf{d}=\mathbf{R}_{\textrm{d}}\mathbf{\Psi}\mathbf{z}.$
(28)

#### Complexity

The computational complexity order of the EM algorithm is mainly determined by
the complexity of equation (20). The complexity order of (19) and (21) is only
$\mathcal{O}(M)$ while the number of the iterations which are required for
convergence is usually very small (e.g., 10-20).

##  IV Simulation Results

In this section, we evaluate the performance of the proposed EM-based
technique via computer simulations. The results have been averaged over $100$
Monte-Carlo realizations.

Figure 1: MSE versus SNR with 3-bit, $T=200$, $N_{\textrm{R}}=15$, $L=9$ and
$\sigma_{\textrm{d}}^{2}=0.012$. Figure 2: MSE versus SNR with 4-bit, $T=200$,
$N_{\textrm{R}}=15$, $L=9$ and $\sigma_{\textrm{d}}^{2}=0.012$. Figure 3: MSE
versus SNR with 5-bit, $T=200$, $N_{\textrm{R}}=15$, $L=9$ and
$\sigma_{\textrm{d}}^{2}=0.012$.

#### System Setup

The mmWave channel is simulated at a frequency of 28 GHz assuming 4 scattering
clusters with a total number of 5 sub-paths for each cluster, i.e., 20
multipaths in total. The instantaneous path gains are modeled based on
Gaussian distribution with zero-mean and unit variance. The UE transmits $L$
Gaussian symbols with repetition coding of length $T$. The average transmit
power is set to $\rho^{1/2}=0.1$. We consider the range of 3-5 bit resolutions
for the ADCs.

We use the classical Rotman lens principles to design all the lenses. The
first stage lens, i.e., right after the URA, consists of $N_{\textrm{ap}}=5$
and $N_{\textrm{bp}}=3$, followed by the second stage lens having
$N_{\textrm{ap}}=N_{\textrm{bp}}=3$. We use number of antennas in this
topology as $N_{\textrm{R}}=15$ and the number of RF chains as $L=9$. The
first stage lens is implemented for beamfoming along azimuth, while the second
stage lenses handle beamforming in elevation. URA antenna elements are
operational at 28 GHz.

#### Estimation Performance

We compare the performance of the proposed EM-based channel estimator with the
conventional EM estimator [31] and the MMSE approach. The results for the
proposed technique and the baseline approaches are shown in Figs. 1-3 for the
cases of 3, 4 and 5 bit ADC resolutions, respectively. We can observe that
proposed EM-based approach outperforms the conventional EM approach and the
MMSE approach for all the different bit cases. For example, at $5$ dB SNR and
$3$-bit case, it can be observed that proposed robust EM-based method performs
$2.25$ dB better and $0.25$ dB better than the SNR performance of the
conventional EM approach and the MMSE approach, respectively. In another
example, at $5$ dB SNR and for the $5$-bit case, the proposed approach is
around $3.5$ dB better and around $0.75$ dB better than the SNR performance of
the conventional EM approach and the MMSE approach, respectively.

##  V Conclusions

This paper considers a mmWave hybrid MIMO RX with a Rotman lens architecture
antenna array and low-resolution ADCs. This design provides a trade-off
between the hardware complexity and the introduced noise to the received
signal. We investigate the performance of the lens-based system with low
resolution ADCs in terms of the mmWave channel estimation. We develop a robust
MAP estimator based on EM iterative algorithm, which outperforms the
conventional EM approach in terms of MSE. This is achieved without increasing
the hardware complexity of the system, while the baseband signal processing
complexity increases only slightly.

## References

  * [1] Cisco Annual Internet Report 2018-23 White Paper, Mar. 2020. [Available Online]
  * [2] Ericsson Mobility Report 2022, pp. 1-40, June 2022. [Available Online]
  * [3] S. Rangan et al., “Millimeter-wave cellular wireless networks: potentials and challenges,” Proc. IEEE, vol. 102, no. 3, pp. 366–385, Mar. 2014.
  * [4] J. Ahmadi-Shokouh et al., “Optimal receive soft antenna selection for MIMO interference channels,” IEEE Trans. Wireless Commun., vol. 8, no. 12, pp. 5893-5903, Dec. 2009.
  * [5] A. Kaushik et al.,“Dynamic RF Chain Selection for Energy Efficient and Low Complexity Millimeter Wave Hybrid MIMO Systems,” IEEE Trans. Green Commun. Netw., accepted, July 2019.
  * [6] A. Kaushik et al., “Joint bit allocation and hybrid beamforming optimization for energy efficient millimeter wave MIMO systems,” _IEEE Trans. Green Commun. Netw._ , vol. 5, no. 1, pp. 119-132, Mar. 2021.
  * [7] E. Vlachos et al., “Radio-frequency chain selection for energy and spectral efficiency maximization in hybrid beamforming under hardware imperfections,” _Proc. Royal Soc. A_ , vol. 476, no. 2244, pp. 1-20, Dec. 2020.
  * [8] A. Kaushik et al., “Hardware efficient joint radar-communicati-ons with hybrid precoding and RF chain optimization,” _IEEE Int. Conf. Commun. (ICC)_ , pp. 1-6, June 2021.
  * [9] A. Kaushik et al., “Green joint radar-communications: RF selection with low resolution DACs and hybrid precoding,” _IEEE Int. Conf. Commun. (ICC)_ , pp. 1-6, May 2022.
  * [10] O. Dizdar et al., “Energy efficient dual-functional radar-communication: Rate splitting multiple access, low-resolution DACs, and RF chain selection,” _IEEE Open J. Commun. Society_ , vol. 3, pp. 986-1006, June 2022.
  * [11] A. Kaushik et al., “Waveform design for joint-radar communications with low complexity analog components,” _IEEE Int. Symp. Joint Commun. Sensing (JC &S)_, pp. 1-5, Mar. 2022.
  * [12] A. Kaushik et al., “Towards 6G: Spectrally efficient joint radar and communication with RF selection, interference and hardware impairments,” _IET Signal Processing_ , vol. 16, no. 7, pp. 851-863, Sept. 2022.
  * [13] M. A. B. Abbasi et al., “Constant-$\epsilon_{r}$ lens beamformer for low-complexity millimeter-wave hybrid MIMO,” IEEE Trans. Microw. Theory Tech., pp. 1-10, 2019.
  * [14] Y. Gao et al., “Rotman lens based hybrid analog digital beamforming in massive MIMO systems: Array architectures, beam selection algorithms and experiments,” IEEE Trans. Veh. Tech., vol. 66, no. 10, pp. 9134-9148, Oct. 2017.
  * [15] E. H. Mujammami et al., “Optimum wideband high gain analog beamforming network for 5G applications,” IEEE Access, vol. 7, pp. 52226-52237, Apr. 2019.
  * [16] M. A. B. Abbasi et al., “Performance of a 28 GHz two-stage rotman lens beamformer for millimeter wave cellular systems,” IEEE EuCAP, Apr. 2019.
  * [17] B. Wang et al., “Spectrum and Energy-Efficient Beamspace MIMO-NOMA for Millimeter-Wave Communications Using Lens Antenna Array,” IEEE J. Sel. Areas Commun., vol. 35, no. 10, pp. 2370-2382, Oct. 2017.
  * [18] A. Kaushik et al., “Energy efficiency maximization of millimeter wave hybrid MIMO systems with low resolution DACs,” _IEEE Int. Conf. Commun._ , Shanghai, China, pp. 1-6, May 2019.
  * [19] G. C. Alexandropoulos et al., “Joint localization and channel estimation for UAV-assisted millimeter wave communications,” _Asilomar Conf. Sig. Syst. Comp._ , pp. 1318-1322, Nov. 2020.
  * [20] G. C. Alexandropoulos and E. Vlachos, “A hardware architecture for reconfigurable intelligent aurfaces with minimal active elements for explicit channel estimation,” _IEEE Int. Conf. Acoustics Speech Sig. Process._ , pp. 9175-9179, May 2020.
  * [21] A. Kaushik et al.,“Efficient channel estimation in millimeter wave hybrid MIMO systems with low resolution ADCs,” IEEE Europ. Sig. Process., Rome, Italy, pp. 1839-1843, Sept. 2018.
  * [22] J. Mo et al., “Channel estimation in broadband millimeter wave MIMO systems with few-bit ADCs,” IEEE Trans. Sig. Process., vol. 66, no. 5, pp. 1141-1154, Mar. 2018.
  * [23] X. Gao et al., “Reliable Beamspace Channel Estimation for Millimeter-Wave Massive MIMO Systems with Lens Antenna Array,” IEEE Trans. Wireless Commun., vol. 16, no. 9, pp. 6010-6021, Sept. 2017.
  * [24] L. Yang et al., “Channel Estimation for Millimeter-Wave MIMO Communications With Lens Antenna Arrays,” IEEE Trans. Veh. Tech., vol. 67, no. 4, pp. 3239-3251, April 2018.
  * [25] X. Gao et al., “Beamspace channel estimation for 3D lens-based millimeter-wave massive MIMO systems,” Int. Conf. Wireless Commun. Sig. Process., Yangzhou, China, pp. 1-5, Oct. 2016.
  * [26] W. Tan et al., “Analysis of different planar antenna arrays for mmWave massive MIMO systems,” IEEE Veh. Tech. Conf., pp. 1-5, June 2017.
  * [27] J. Brady et al., “Beamspace MIMO for millimeter-wave communications: system architecture, modeling, analysis, and measurements”, IEEE Trans. Antenn. Propag., vol. 61, no. 7, pp. 3814-3827, Jul. 2013.
  * [28] L. Dai et al., “Beamspace channel estimation for millimeter-wave massive MIMO systems with lens antenna array”, in 2016 IEEE/CIC Int. Conf. Commun. China (ICCC), pp. 1-6, July 2016.
  * [29] M. A. B. Abbasi et al., “Lens based beamformer for low-complexity millimeter wave cellular systems,” ESA Workshop Millimetre-Wave Tech. Appl., Dec. 2018.
  * [30] B. Widrow and I. Kollar, “Quantization noise: Roundoff error in digital computation, signal processing, control, and communications,” Cambridge University Press, Cambridge, UK, 2008.
  * [31] M. R. Gupta and Y. Chen, “Theory and use of the EM algorithm,” Found. Trends Sig. Process., vol. 4, no. 3, pp. 223-296, Mar. 2011.
  * [32] A. Mezghani et al., “Multiple parameter estimation with quantized channel output,” Proc. ITG WSA, pp. 143-150, Feb. 2010.
  * [33] R. C. Hansen, “Design trades for Rotman lenses,” IEEE Trans. Ant. Propag., vol. 39, no. 4, pp. 464-472, Apr. 1991.