Fast and Space-optimal Low-rank Factorization in the Streaming
Model With Application in Differential Privacy
Jalaj Upadhyay∗
Pennsylvania State University

arXiv:1604.01429v3 [cs.DS] 20 May 2016

jalaj@psu.edu

Abstract
In this paper, we consider the problem of computing a low-rank factorization of an m × n matrix in
the general turnstile update model. We consider both the private and non-private setting.
1. In the non-private setting, we give a space-optimal algorithm that computes a low-rank factorization. Our algorithm maintains three sketches of the matrix instead of five as in Boutsidis et al.
e
(STOC 2016). Our algorithm takes O(1)
time to update the sketch and computes the factorization
in time linear in the sparsity and the dimensions of the matrix.
2. In the private setting, we study low-rank factorization in the framework of differential privacy and
under turnstile updates. We give two algorithms with respect to two levels of privacy. Both of our
privacy levels are stronger than earlier studied privacy levels, namely that of Blocki et al. (FOCS
2012), Dwork et al. (STOC 2014), Hardt and Roth (STOC 2012, STOC 2013), and Hardt and
Price (NIPS 2014).
(a) In our first level of privacy, Priv1 , we consider two matrices as neighboring if their difference
has a form uvT for some unit vectors u and v. Our private algorithm with respect to Priv1
matches the optimal space bound up to a logarithmic factor and is optimal in the terms of
the additive error incurred. The algorithm is also efficient and takes time linear in the input
sparsity of the matrix and quadratic in min {m, n}. p
Our bound quantitatively improve the
result of Hardt and Roth (STOC 2012) by a factor of k log(1/δ) when m ≤ n, a scenario
considered by Hardt and Roth (STOC 2012).
(b) Our second level, Priv2 , generalizes Priv1 . In Priv2 , we consider two matrices as neighboring
if their difference has unit Frobenius norm. Our private algorithm with respect to Priv2 is
computationally more efficient than our first algorithm – it uses O(log(m+n)) time to update
and computes the factorization in time linear in the input sparsity and the dimensions of the
matrix. This algorithm incurs optimal additive error and uses optimal space when n  m.

∗

Research supported by NSF award IIS-1447700.

i

1

Introduction

In the list compiled by Dongarra and Sullivan [18] that “assemble the 10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century”, the fourth entry
is “The Decompositional Approach to Matrix Computation”. Technically, matrix decomposition is not
an algorithm, but its inclusion is often argued for by its immense application in many areas of computation [47]. An incomplete list of applications of matrix factorization includes data mining [4], recommendation systems [21], conic fitting problems [67], information retrieval [55, 59], system and control [46], web
search [1, 44], chemometrics [60, 65], clustering [14, 19, 48], solving PDE [30, 31], and learning distributions [2, 41]. For example, consider the following two graphs, G1 and G2 , defined over the set of vertices
V := {Companies, Universities}, where Companies is the set of all companies and Universities is the set of
all the universities in a particular country:
Graph 1. In the graph G1 , there is an edge between two nodes (u, v) ∈ V if there is a student who did his
undergraduate from a university u and then moved to the company/university v. The weight on the edge is
the number of all such students who moved from u to v after graduation.
Graph 2. The graph G2 is a generalization of G1 . The contribution of a person to the weight of an edge
between two nodes (u, v) is proportional to the time spent after moving from u to v since graduation.
The weight on every edge (i, j) depends on the number of undergraduates who moved from i to j, this
makes such graphs vital for companies and universities to target incoming graduates. One would, therefore,
like to build a data mining system or a recommendation system based on the statistics of these graphs or
perform efficient search of any entry in these graphs. In order to build such a system, let us look closely at
some of the features of these graphs. The adjacency matrices of G1 and G2 have large Frobenius norms and
can be dense (depending on the number of graduating students). Therefore, storing the graphs requires a lot
of storage. Since students get an offer in an arbitrary order; G1 is updated in a turnstile manner. Likewise
people change job in arbitrary order during their career, i.e., G2 is updated in a turnstile manner. This makes
storing and updating a sketch, that allows efficient construction of a recommendation system or perform
data-mining, challenging.
Low-rank approximation. To assuage these issues, a general technique used in the literature is to compute
a low-rank approximation (LRA) of the adjacency matrix in the turnstile update model and use this approximation to perform all the computational tasks. This technique is used by many previous works where matrix
factorization is used. As a result, LRA of large matrices (and not just adjacency matrices of graphs) has
received a lot of attention in the recent past. Most of the proposed algorithms used either random sketching [11, 40, 58] or random sampling [3, 20, 22, 15, 29, 56, 57]. The run-time of these algorithms were
improved substantially in subsequent works [13, 16, 45, 50, 54, 53, 58]. However, these works either assumed that the matrix is static or used a lot of storage when matrices are updated in the general turnstile
manner. Recently, Boutsidis et al. [8] gave the first space-optimal and low communication cost algorithm to
compute LRA; however, they do not optimize the computational cost of their algorithm.
Low-rank approximation and privacy. There is also a natural privacy concern associated with such graphs
and many applications where LRA is used. The privacy issue has been recently exemplified by the deanonymization of Netflix datasets [52] and Hunch and Amazon [9]. In the latter case, no data is directly released (as
in the Netflix challenge), but items similar to a given item are shown to the users. This was one of the
motivations for the work of McSherry and Mironov [49]. Even training data of learning theoretic algorithms
have natural privacy concerns. This motivated the line of research of differentially private learning [37, 61].

1

Therefore, a more natural requirement would be to compute low-rank approximation of a matrix while providing some robust privacy guarantee, like differential privacy [24]. Differentially-private LRA has been
studied by many recent works (see, Section 1.3 for more details), but these algorithms are optimized for the
additive error incurred, and not for the space used by the algorithm or the computational cost to compute
the LRA. Moreover, except for Dwork et al. [28] and Upadhyay [63], none of the known results work in
the streaming model. The algorithms of Dwork et al. [28] and Upadhyay [63] works only in the row-wise
update model and not in the general turnstile update model as in G1 and G2 . Further, Dwork et al. [28]
approximates only the right singular vectors.

1.1

Problem Description

In this paper, we study time-efficient and sublinear space algorithms for computing low-rank factorization
when the input matrix is updated in a general turnstile manner (see Problem 1). If there were no space or time
constraints, then computing a low-rank factorization is equivalent to computing a low-rank approximation
and we can use any of the earlier known results. However, under the time and space constraints considered
in this paper, it is not clear how can we use a low rank approximation to get a low-rank factorization. In order
to keep our results as general as possible, we do not assume any structure in the matrices, like symmetry or
incoherence.
In the non-private setting, our goal is to construct a data-structure such that (i) the data-structure uses
space sub-linear in the size of the data and its overall update time is linear in the sparsity of the private
matrix, (ii) performing the low-rank factorization using these data-structures leads to a small multiplicative
error. In the private setting, we further require that the data-structure does not lead to a privacy leak of
the entries in the input matrix. We consider differential privacy for the privacy framework. Differential
privacy is a well-established notion of privacy with many desirable features such as robustness and modular
composition.
Definition 1. A randomized algorithm M gives (ε, δ)-differential privacy, if for all neighbouring databases
A, A0 and all subsets S in the range of M, Pr[M(A) ∈ S] ≤ exp(ε)Pr[M(A0 ) ∈ S] + δ, where the
probability is over the coin tosses of M.
Since we consider differential privacy in the streaming setting, we define it in terms of neighboring
streams.
Definition 2. A randomized algorithm M gives (ε, δ)-differential privacy in the streaming model, if for all
neighbouring data-streams A, A0 and all subsets S in the range of M, Pr[M(A) ∈ S] ≤ exp(ε)Pr[M(A0 ) ∈
S] + δ, where the probability is over the coin tosses of M.
Equipped with the above definition, we can define our model. We enumerate the key aspects of the
(differentially private) turnstile update model of computation as follows.
• There are three entities: a stream generator S, a (database) curator C, and an analyst A. The stream
generator S has a database matrix as input which it streams to the curator.
• S starts the process at time τ = 0 and C initializes its data structure to D0 . The stream generator S
provides C with the database matrix in a general turnstile manner, i.e., the stream consists of pairs
(q, cτ ), where q ∈ [m] × [n] is the location and cτ is the item to be added or deleted at location q.
• C update its data structure to Dτ using Dτ −1 and the data received during the time τ . At any time,
C uses space that is at most sublinear in the size of the streamed matrix. and takes total time that is
linear in the length of the stream.

2

• Once the stream is over at τ , A requests C to perform certain tasks to which C responds using only
Dτ .
• In the setting of differential privacy, we further require that the responses of the curator should also
satisfy Definition 2 for neighboring streams.
We can now define the problem that we consider in this paper.
Problem 1. (α, β, γ, k)-LRF. Given parameters α, β, γ, a private m × n matrix A (received in a turnstile
e k, Σ
e k , and V
e k such that
streaming model) and the target rank k, find a rank-k matrix factorization U


e kΣ
e kV
e T kF ≤ (1 + α) min kA − Ak kF + γ ≥ 1 − β.
Pr kA − U
k
rank(Ak )≤k

When privacy is also a concern, we require that the algorithm that computes (α, β, γ, k)-LRF also preserves (ε, δ)-differential privacy. When an algorithm only outputs a rank-k matrix (and not a factorization),
then we say that the algorithm computes (α, β, γ, k)-low rank approximation of the input matrix A.
Central to the notion of differential privacy is the concept of neighboring database. In this paper, we
consider databases presented in the form of matrices. To motivate our definition of neighboring databases,
we refer back to the graphs G1 and G2 . Graphs like G1 are well studied in the literature of differential privacy
(see, for example, [6, 28, 34, 33, 62, 63]) under the privacy level known as edge-level privacy. In edge-level
privacy, the presence or absence of a person corresponds to change in a single edge. On the other hand,
graphs like G2 are not very well studied. One of the main problems with such graphs is that a person might
have been in many places during his career; thereby, presence or absence of a person would be reflected on
many edges. The straightforward applications of earlier results on edge-level privacy [6, 34, 62, 63] to the
graphs of form G2 would lead to a large privacy loss. In this paper, we ask the question whether we can
achieve comparable privacy loss in the scenario as in graph G2 without compromising on the correctness or
privacy loss. This motivates us to consider a stronger privacy level than edge-level privacy. We define our
privacy level next.
Granularity of privacy. We consider two different levels of privacy. In the first level, Priv1 , two databases
are neighboring if the difference of their corresponding matrix representation has the form uvT for some
unit vectors u and v. In the second level, Priv2 , we consider two databases as neighboring if the difference
of their matrix representations has Frobenius norm at most 1. Note that Priv1 is a special case of Priv2 . We
consider two streams neighboring if they are formed by streaming neighboring matrices.

1.2

Our Contributions and Technical Overview

In this paper, we do not assume any upper bound on the Frobenius norm of the input matrix. For example,
adjacency matrices corresponding to both G1 and G2 can have arbitrary large Frobenius norm. In fact, none
of our results depend on the Frobenius norm, unlike some private algorithms [28, 34]. All of our results are
for the turnstile update model. Our contributions in this paper are as follows.
1. Non-private fast and space-optimal algorithm. Our first result is a space-optimal and update time
efficient algorithm for outputting LRF of a matrix in the turnstile update model. Our algorithm is
different from Boutsidis et al. [8]. We show that one only need three sketches (one for approximating
row-space, one for approximating column-space and one for approximating the matrix), and not five
sketches as used by Boutsidis et al. [8], to get similar bounds. Even if one does count the update-time
efficiency, we believe that maintaining three sketches instead of five would be more efficient in actual
implementation (and not asymptotic analysis).
3

Theorem (informal statement of Theorem 12). Let A be an m × n matrix with nn(A) non-zero
eβ ((n + m)kα−1 ) space and runs in time O(nn(A)) +
entries. Then there is an algorithm that uses O
2
−2
2
−2
3
−3
eβ (nk α + mk α + k α ) to compute a k-rank factorization Uk Σk VT of a matrix A such
O
k
eβ (·) hides a
that, with probability 1 − O(β), kUk Σk VkT − AkF ≤ (1 + α)kA − Ak kF , where O
factor of poly (log(1/β)).
To prove our result, we give an alternate proof of one of the intermediate theorems of Boutsidis et
al. [8]. Our alternate proof uses two optimization problems and uses the solution to these optimization
problems. We feel that our proof is simpler. It also gives explicit optimum solutions to the two
problems, which makes it easy to extend to (and get a tight bound in) the case of private low-rank
factorization. We also prove a lemma (Lemma 13) that gives the best rank-k approximation of a
matrix A in the terms of column-space and row-space of a sketch of the matrix A.
Optimality of the result. Clarkson and Woodruff [11] showed that, when the matrix is streamed in
the turnstile model, any randomized algorithm that solves (α, 1/6, 0, k)-low rank approximation of an
m × n matrix requires Ω((m + n)kα−1 ) words space. Therefore, our algorithm uses optimal space,
up to a logarithmic factor.
2. Space-optimal private streaming algorithm. We also convert our non-private algorithm to give a
private algorithm that is space-optimal under a stronger privacy level, Priv1 (see, Section 1.2.1) in the
general turnstile update model. The following is an informal statement of Theorem 15.
Theorem (informal statement of Theorem 15). Let A be an m × n matrix with nn(A) non-zero
entries. Let p = max {m, n}. Then there is an (ε, δ)-differentially private algorithm that receives the
eδ ((m + n)(k + α−1 )α−1 ) space, and outputs a
private matrix in a turnstile streaming model, uses O
T
eδ (nk 2 α−2 + mk 2 α−3 + k 3 α−4 ) such that
rank-k factorization Uk Σk Vk of A in time O(nn(A)) + O


p
p
kA − Uk Σk VkT kF ≤ (1 + α)kA − Ak kF + Oδ ε−1
kp(1 + 1/α) + kmn/(p + pα) ,
eδ (·) hides a factor of poly (log(1/δ)) and Ak is the best rank-k approximation.
where O
To preserve the privacy, we use both input and output perturbation. We also need to take care of the
fact that Priv1 is more general than the earlier works [6, 63, 64] (see Section 1.2.1). This requires us to
generalize the previous privacy results [6, 63]. The specific choice of perturbation is crucial in getting
a tight utility bound while preserving privacy. For example, one possibility could have been the input
perturbation of the sketches Yr = ΨA and Yc = AΦ, for appropriate Φ and Ψ, followed by a
multiplication by Gaussian matrices Ω1 and Ω2 as in [6, 63, 64]. If m ≤ n, one can prove that Yc Ω1
is private, but since, Ω2 Yr does not have a full-column rank, the multivariate Gaussian distribution
is not defined. An attempt to consider the subspace orthogonal to the kernel space of Yr does not
work because we cannot guarantee that both ΨA and ΨA0 have the same kernel for neighboring
matrices A and A0 . Therefore, the privacy proof would not follow. On the other extreme, if we add
b + N and Yr = ΨA + N0 , then we get
random noise matrices to compute the sketches Yc = AΦ
†
T
† † 0
kN(AT
k Φ) (ΨAΦ(Ak Φ) ) N kF as one of the additive terms. This term can be arbitrary large if
any of the singular values of A is too small, resulting in a large additive error. Our algorithm uses
input perturbation with a careful choice of parameters to one of the sketches and output perturbation
to the other two sketches so that we preserve privacy and still not incur a large additive error. To get
a tight bound on the additive error due to one of output perturbations, we need our alternate proof of
one of the theorems of Boutsidis et al. [8].

4

Optimality of the result. We adapt the proof of Clarkson and Woodruff [11] to show that the space
required by any randomized algorithm to solve (α, 1/6, O(m + n), k)-LRA is Ω((n + m)kα−1 )
(see, Theorem 41 for a formal statement). In other words, the space bound in the above
√ theorem is
optimal when k ≥ 1/α. Recall that Hardt and Roth [34] and Upadhyay [63] set α = 2 − 1. In other
words, with their choice of parameters, we match the lower bound when k ≥ 3.
√
Hardt
and Roth [34] showed that any differentially private low-rank approximation incurs an Ω( kn+
√
km) additive error by showing a reduction to the linear reconstruction attack [17]. They showed the
lower bound when the differentially private mechanism can access the private matrix as many times
as possible. Our bound matches the lower bound, up to a small multiplicative factor, while allowing
the private mechanism to access the private matrix only in a turnstile manner.
3. Optimal error private streaming algorithm. Our last contribution is an algorithm that has constant
update time and computes private low-rank factorization efficiently with an optimal additive error
under the stronger level of privacy, Priv2 (see, Section 1.2.1).
Theorem (informal statement of Theorem 28). Let A be an m × n matrix with nn(A) non-zero
entries. Then there is an (ε, δ)-differentially private algorithm that receives the private matrix in a
eδ ((m + nα−2 )kα−2 ) space, and
turnstile streaming model, updates in O(log(m + n)) time, uses O
eδ (nk 2 α−3 + mk 2 α−5 + k 3 α−6 ) time
outputs a rank-k factorization Uk Σk VkT of A in O(nn(A)) + O
such that
s

! !
√
n(1
+
α)
1
1
eδ
(1 + α) km +
kA − Uk Σk VkT kF ≤ (1 + α)kA − Ak kF + O
k+
,
3
α
α
ε
eδ (·) hides a factor of poly (log(1/δ)) and Ak is the best rank-k approximation.
where O
Optimality of the result. The above result matches the run-time of the
√ most√efficient non-private
algorithm up to a factor of α−3 [13, 50]. We match the lower bound of Ω( kn+ km) on the√additive
error given by Hardt and Roth [34], up to a small multiplicative factor (and constant if α = 2 − 1),
while allowing the private mechanism to access the private matrix only once and that, too, in a turnstile
manner.
1.2.1

Comparison with Previous Works

eβ (nn(A)+
Comparison of Non-private Algorithm. In the non-private setting, our algorithm runs in time O
2
2
3
3
(m + n)k /α + k /α ) and uses O((n + m)k log(1/β)/α) space. Clarkson and Woodruff [13] achieves a
eβ (nn(A) + mk 2 /α2 + nk 2 /α4 ) and uses O
eβ (mk/α + nk/α2 ) space. Boutsidis et al. [8] gave
run time of O
the first space-optimal algorithm for low-rank approximation; however, they run in time O(mnk). After
learning of this paper, Woodruff [66] showed that one can obtain the similar bound by using the embedding
of Clarkson and Woodruff [13] in the protocol of Boutsidis et al. [8]. We tabulate our result with previous
work in Table 1.
Comparison of private algorithms (privacy level). The granularity of privacy used in this paper is more
general than Blocki et al. [6], Dwork et al. [28], Hardt and Roth [34, 35], Hardt and Price [33], and Upadhyay [63]. One can consider that Priv1 and Priv2 lies between the node-level privacy [43] and edge-level
privacy.
For example, in the adjacency matrix corresponds to G2 , every edge e = (u, v) is given a weight
P
(t
/t
i i,e i ), where ti,e is the time spent by person i after moving from u to v and ti is the total time lapsed
since his/her graduation. In this case, Priv2 corresponds to the presence or absence of a single individual in
the data. However, this is not captured by either the edge-level privacy or by the node-level privacy.
5

Clarkson-Woodruff [13]
Boutsidis et al. [8]
This work
Lower Bound

Time
eβ (nn(A) + mk 2 /α2 + nk 2 /α4 )
O
O(mnk + (m + n)k 2 /α)
eβ (nn(A) + (m + n)k 2 /α2 + k 3 /α3 )
O
Ω(nn(A) + (m + n)k)

Space
eβ (mk/α + nk/α2 )
O
O((n + m)k log(1/β)/α)
O((n + m)k log(1/β)/α)
Ω((n + m)k/α) [11]

Table 1: Comparison of Non-private Algorithms

Theorem 28
Problem 1

(ε, δ)-differential privacy
Theorem 15
(ε, δ)-differential privacy
Hardt and Roth [34]

Problem 2

(ε, δ)-differential privacy
Hardt and Roth [34]
(ε, δ)-differential privacy
Upadhyay [63]
(ε, δ)-differential privacy

Neighbouring Data
kA − A0 kF = 1 
α,

τ =O

Assumptions
No assumptions 

q
√
 √log(1/δ)
1
k
+
(1 + α) km + n(1+α)
α3
α
ε

A − A0 = uvT 
No assumptions

√
√
√
k(m+n)(1+α)
k(m+n)
k (1+α)
α,
τ =O
+
+
αε
ε(1+α)
εα2
A − A0 = es vT

√

α = O(1), τ = O

km log(k/δ)
ε

A − A0 = es vT
α = O(1),
A − A0 = es vT
α = O(1),

τ =O

√

τ =O

Incoherent matrix

q
pn
+ k µ0 kAkF log(k/δ)
ε
m

No coherence assumption


km log(k/δ)
ε



k2

√

√

n
+ k log(1/δ)
ε
No assumptions


n+m log(k/δ)
ε

Table 2: Comparison of Models for Differentially-private k-Rank Approximation (β = O(1), u and v are unit vectors,
es is the s-th standard basis, and µ0 is the coherence of the private matrix).

Comparison of private algorithms (problem studied). There are few key differences between the problem
that we study and the problems studied in previous works. All the previous private algorithms compute lowrank approximation (either of the matrix or its covariance). Though it is possible to compute the factorization
of their outputs, this would incur an extra O(mn2 ) running time for the factorization of an m × n rank-k
matrix. Moreover, they require O(mn) space just to save the output (Dwork et al. [28] requires O(n2 ),
but they work with covariance matrices). We do not assume any upper bound on the Frobenius norm of
the private matrix as in previous works (the result of Hardt and Roth [34] is applicable when m  n and
√
√
kAkF = O( n) and Dwork et al. [28] assume a normalized row assumption, i.e, kAkF = O( m)).
On the other hand, G1 and G2 can have arbitrary large Frobenius norm. Apart from this, previous works,
like [28, 42, 34, 33], compute LRA under the spectral norm and Dwork et al. [28] only approximate the rightsingular vector. On the other hand, our algorithms outputs an approximation to both right and left singular
vectors. We give the technical descriptions and the differences between Problem 1 and all the previously
studied problems in Appendix C.
Quantitative comparison of private algorithms. Hardt and Roth [34] and Upadhyay [63]) studied LRA in
a model closest to ours. Therefore, we only compare this work with the results of Hardt and Roth [34] and
Upadhyay [63]. We give a comparison of the results in Table 2. Problem 2 differs from Problem 1 only in
the sense that Problem 2 only requires the low-rank approximation while Problem 1 also requires low-rank
factorization. Below, we enumerate the key differences between our result and previous results [34, 63].
p
1. Additive error. Both of our bounds improves on Upadhyay [63] by a factor of k 3/2 α2 log(1/δ). To
make a reasonable comparison with Hardt and Roth [34], we consider their result with no-coherence
6

√
assumption and our result whenpα = 2 − 1. Combining Theorem 4.2 and 4.7 in Hardt and Roth [34]
√
results in an additive error O(( km log(1/δ) + ck log(k/δ) n)ε−1 ), where c is the maximum entry
inpthe projection matrix. In other words, Theorem 15 improve the result of Hardt and Roth [34] by a
c k log(1/δ) factor when m ≤ n.
2. Time and space efficiency. The result of Hardt and Roth [34] is applicable when the private matrix is
not dense (see the discussion in Hardt and Roth [34, Sec 1.1]). However, their algorithm does not use
low-sparsity of the input matrix. On the other hand, the running and update time of our algorithms
depends on the number of non-zero entries of the input matrix and uses optimal space. Hardt and
Roth [34] and Upadhyay [63] uses O(kmn) time and O(mn) space. Therefore, even if the matrix is
not sparse, our algorithms are still more efficient in terms of both the space and time.
3. Streaming constraints. Hardt and Roth [34] is a private version of the two-pass algorithm of Halko
et al. [32]. The algorithm of Upadhyay [63] is one-pass, but assumes that the matrix is streamed
row-wise. A row-wise update is an easier problem (with respect to the space required) compared to
the turnstile update model in the non-private setting as illustrated by Clarkson and Woodruff [11].
4. Applicability. The result of Hardt and Roth [34] is applicable when the Frobenius norm is bounded
√
by O( n) and m  n. We do not put such restrictions on the size of m and n and the Frobenius
norm.

1.3

Related Work

There has been a lot of work that used random projection [11, 40, 58] or random sampling [3, 20, 22, 15, 29,
56, 57] to give low-rank approximation. Many of the latter algorithms were improved substantially in the
follow-up work [8, 13, 16, 45, 50, 54, 58]. Differential privacy was introduced by Dwork et al. [24]. Since
then, many algorithms for preserving differential privacy have been proposed in the literature (see, Dwork
and Roth [26]). Dwork et al. [25] first considered streaming algorithms with privacy under the model of
pan-privacy, where the internal state is known to the adversary. Subsequently, there have been some works
on online private learning [28, 37, 61] for various tasks. There are some recent works on differentially
private LRA as well. Blum et al. [7] first studied this problem in the Frobenius norm. This was improved by
Hardt and Roth [34] under the low coherence assumption. Upadhyay [63] later showed that one can make
the two-pass algorithm of Hardt and Roth [34] single-pass. Differentially-private LRA has been studied in
the spectral norm as well by many works [10, 42, 35, 33]. Recently, Dwork et al. [28] gave a tighter analysis
of the algorithm of Blum et al. [7] and used it to give a private online algorithm for covariance matrices.
Organization of the paper. In Section 3, we give our non-private algorithm for LRF in the general turnstile
update model. In Section 4, we transform our non-private algorithm to a private algorithm under Priv1
while incurring optimal additive error. In Section 5, we give an algorithm that has efficient update time
under more finer granularity of privacy, Priv2 .

2

Notations, Preliminaries, and Known Results

We let N to denote the set of natural numbers. We use bold-face capital letters to denote matrices and boldface small letters to denote vectors. We denote by 0m×n the all-zero m × n matrix and by In the n × n
identity matrix. For a matrix A, we denote the best k-rank approximation of A by [A]k and its Frobenius
norm by kAkF . The singular-value decomposition (SVD) of an m × n rank-r matrix A is a decomposition
of A as a product of three matrices, A = UΣVT such that U ∈ Rm×r and V ∈ Rn×r has orthonormal
7

columns and Σ ∈ Rr×r is a diagonal matrix with singular values of A on its diagonal. For a matrix A,
we use the symbol r(A) to denote its rank and ∆(A) to denote its determinant. If A = UΣVT with the
diagonal entries of Σ being {σ1 , · · · , σr }, then ∆(A) = Πi σi . The Moore-Penrose pseudo-inverse of a
matrix A = UΣVT is denoted by A† and has a SVD A† = VΣ† UT , where Σ† consists of inverses of
only non-zero singular values of A. A matrix A has a left-inverse (right-inverse, respectively) if and only if
it has full column rank (full row rank, respectively). If A has a left-inverse, then A† = (AT A)−1 AT and if
A has right-inverse, then A† = AT (AAT )−1 .
Probability theory. We use the notation Rad(p) to denote a distribution with support ±1 such that +1 is
sampled with probability p and −1 is sampled with
 probability 1 −p. An n × n Walsh-Hadamard matrix
Hn/2 Hn/2
Hn is constructed recursively as follows: Hn =
and H1 := 1. A randomized WalshHn/2 −Hn/2
Hadamard matrix Wn is formed by multiplying Hn with a diagonal matrix whose diagonal entries are
picked i.i.d. from Rad(1/2). We drop the subscript n where it is clear from the context.
Given a random variable x, we denote by N (µ, ρ2 ) the fact that x has a normal Gaussian distribution with mean µ and variance ρ2 . The multivariate Gaussian distribution is a generalization of univariate
Gaussian distribution. Let µ be an N -dimensional vector. An N -dimensional multivariate random variable, x ∼ N (µ, Λ), where Λ = E[(x − µ)(x − µ)T ] is the N × N covariance matrix, has the probability
−xT Λ† x/2
density function given by PDFX (x) := √ e
. If Λ has a non-trivial kernel space, then the multi(2π)r(Σ) ∆(Λ)

variate distribution is undefined. However, in this paper, all our covariance matrices have only trivial kernel.
Multivariate Gaussian distributions is invariant under affine transformation, i.e., if y = Ax + b, where
A ∈ RM ×N is a rank-M matrix and b ∈ RM , then y ∼ N (Aµ + b, AΛAT ).
Random Projections. We use various concepts and results from the theory of random projections.
Definition 3. Let α, β > 0. A distribution D over t × n random matrices satisfies (α, β)-Johnson-Lindenstrauss
property (JLP) if, for any unit vector x ∈ Rn , we have kΦxk22 = (1±α) with probability 1−β over Φ ∼ D.
Definition 4. A distribution DR of t × m matrices satisfies (α, β)-subspace embedding for generalized
0
regression if it has the following property: for any matrices P ∈ Rm×n and Q ∈ Rm×n such that r(P) ≤ r,
e − QkF ≤ (1 +
e = argminX kΦ(PX − Q)kF , then kPX
with probability 1 − β over Φ ∼ DR , if X
α) minX∈Rn×n0 kPX − QkF .
Definition 5. A distribution DA over t × m matrices satisfies (α, β)-affine embedding if it has the following
0
property: for any matrices P ∈ Rm×n and Q ∈ Rm×n such that r(P) ≤ r, with probability 1 − β over
0
S ∼ DA , simultaneously for all X ∈ Rn×n , kS(AX − B)k2F = (1 ± α)kAX − Bk2F .
We use the symbol DR to denote a distribution that satisfies (α, β)-subspace embedding for generalized regression. We use the symbol DA to denote a distribution that satisfies (α, β)-affine subspace
embedding. One example of a distribution that satisfies DR with t = O(α−2 log(1/β)) is the distribution of random matrices whose entries are sampled i.i.d. from N (0, 1/t). Sarlos [58] observed that a
random matrix sampled from a distribution that satisfies the JLP is also a (α, β)-subspace embedding
for generalizedp
regression for rank-r matrix as long as it approximates matrix multiplication with multiplicative error α/r. The latter follows from the standard result on any transform with JLP with projected dimension t = O(r + log(1/β)/α2 ). Using Indyk and Motwani [36], we only need to project to
a t = O(rα−1 log(1/β))-dimensional subspace. Since random Gaussian matrices satisfies the JLP, this
implies the following fact.
0

Fact 6. ([39, 58]) Let P ∈ Rm×n be a matrix of rank r and Q ∈ Rm×n be an m × n0 matrix. Let D
be a distribution of matrices over Rt×n with entries sampled i.i.d. from N (0, 1/t). Then there exists a
8

Initialization. Set t = O(kα−1 log k), v = O(kα−2 log k). Sample Φ ∈ Rn×t , Ψ ∈ Rt×m such that ΦT ∼ DR
and Ψ ∼ DR satisfies Lemma 7. Sample S ∈ Rv×m , T ∈ Rv×n such that S ∼ DA and TT ∼ DA satisfies Lemma 8.
Initialize an all zero matrices, Yc := 0m×t , Yr := 0t×n , and Z := 0v×v .
Update rule. Suppose at time τ , the stream is (iτ , jτ , Aτ ), where (iτ , jτ ) ∈ [m] × [n]. Update the matrices by the
following rule: (i) (Yc )iτ ,j = (Yc )iτ ,j + Aτ Φjτ ,j for all 1 ≤ j ≤ t, (ii) (Yr )i,jτ = (Yc )i,jτ + Aτ Ψi,jτ for all
1 ≤ j ≤ t, and (iii) Zi,j = Zi,j + Si,iτ Aτ Tj,jτ for all 1 ≤ i, j ≤ v.

Computing the factorization. Once the matrix is streamed, we follow the following steps.
1. Compute a matrix U ∈ Rm×t whose columns are orthonormal basis for the column space of Yc and matrix
V ∈ Rt×n whose rows are the orthonormal basis for the row space of Yr .
e sΣ
e sV
e T . Compute a SVD of VTT . Let it be U
e tΣ
e tV
e T.
2. Compute a SVD of SU. Let it be U
s

t

0 0 0T
e sΣ
e † [U
e T ZV
e t ]k Σ
e †U
eT
3. Compute a SVD of V
t t . Let it is be U Σ V .
s
s

4. Output the matrix UU0 compromising of left singular vectors, diagonal matrix Σ0 , and the matrix VT V0 with
right-singular vectors. Denote by Mk = UU0 Σ0 (VT V0 )T .
Figure 1: Space-efficient Low-rank Factorization (Optimal-Space-LRF)

t = O(r/α log(r/β)) such that D is an (α, β)-subspace embedding for generalized regression.
We use the following known results shown by Clarkson and Woodruff [12].
Lemma 7. ([12, Lem 41, Lem 46]) There is a distribution DR over Rt×m that satisfies (i) (α, β)-subspace
embedding for generalized regression, and (ii) if t = O(α−2 log2 m), then for any m × n matrix D,
kΦDk2F = (1 ± α)kDk2F , (iii) if t = O(r/α log(r/α) log(1/β)), such that, if R ∼ DR , then RQ can
be computed in O(nn(Q) + tn0 logt) time for rank r matrices P.
Lemma 8. [12, Thm 39, Thm 42]) There exists a distribution DA over Rv×m that (i) DA satisfies (α, β)affine embedding, and (ii) if v = Θ(α−2 ) and an m × d matrix D, kSDk2F = (1 ± α)kDk2F , and (iii) if
0
v = O(p/α2 log(r) log(1/β)), then for any rank r matrix D ∈ Rm×n and a matrix E ∈ Rm×n , SE and
SD can be computed in O(nn(D)) + nn(E)) + O((n + n0 )v 2 log v) time.
Differential privacy. We use the following results about differential privacy in this paper.
Lemma 9. (Post-processing [23]). Let M(D) be an (ε, δ)-differential private mechanism for a database D
, and let h be any function, then any mechanism M0 := h(M(D)) is also (ε, δ)-differentially private.
Theorem 10. (Composition [27]). Let ε0 , δ0 ∈ (0, 1), and δ 0 > 0. If M1 , · · · , M` are each (ε, δ)-differential
private mechanism, then the mechanism M(D) := (M1 (D), · · p
· , M` (D)) releasing the concatenation of
each algorithm is (ε0 , `δ + 0 + δ 0 )-differentially private for ε0 < 2` ln(1/δ 0 )ε0 + 2`ε20 .
Theoremp
11. (Gaussian mechanism [23].) Let x, y ∈ Rn be any two vectors such that kx − yk2 ≤ c. Let
−1
ρ = cε
log(1/δ) and g ∼ N (0, ρ2 )n be a vector with each entries sampled i.i.d. Then for any s ⊂ Rn ,
Pr[x + g ∈ s] ≤ eε Pr[y + g ∈ s] + δ.

3

Optimal Space Streaming Algorithm for Low-rank Factorization

In this section, we present our non-private algorithm. Our algorithm is different from that of Boutstidis et
al. [8] and has a nice symmetric form which allows us to extend this algorithm to the private setting. Our
algorithm maintains three sketches (namely, Yr = ΨA for approximating the row-space, Yr = AΦ for
approximating the column-space and Z = SATT for approximating the matrix), instead of five sketches as
maintained by Boutsidis et al. [8], to get similar bounds. The main theorem of this section is stated below.

9

Theorem 12. Let m, n ∈ N and α, β be the input parameters. Let k be the desired rank of the low-rank
e Σ,
e V
e outputted by the
factorization. Given an m × n matrix A in a turnstile model, the factorization U,
algorithm Optimal-Space-LRF, presented in Figure 1, is a k-rank factorization of the matrix A such that:
1. With probability 1 − O(β) over the random coins of the algorithm Optimal-Space-LRF,
eΣ
eV
e T.
kMk − AkF ≤ (1 + α)kA − [A]k kF , where Mk = U
2. Optimal-Space-LRF uses at most O((m + n)kα−1 log(1/β) log k) space.
3. The update-time of Optimal-Space-LRF is O(log(n + m)). The total time for the computation of
low-rank factorization by Optimal-Space-LRF is O(nn(A) log(1/β))+O((m+n) log(1/β)k 2 α−2 )
time.
Proof. Part 2 of Theorem 12 follows straightforwardly from the choice of v and t and the dimensions of all
the sketches, Yc = AΦ, Yr = ΨA, and Z = SATT . For the update time in part 3 of Theorem 12, note
that Φ and Ψ operates in input-sparsity time, which is constant, plus an O(log(m + n)) term. The same is
true for the update time of Z. For the factorization time in part 3 of Theorem 12, we need to analyze the
running time of the algorithm presented in Figure 1. We analyze it as follows.
1. Computing Yc requires O(nn(A)) + mt2 time and computing Yr requires O(nn(A)) + nt2 time.
e
Therefore, computing Yc and Yr requires O(nn(A)) + O((m
+ n)k(k + α−1 )) time. Computing Z
e 2 /α4 + nn(A)) + O(nk(k
e
requires O(k
+ α−3 ))
e
2. Computing the orthonormal basis U and V requires nt2 + mt2 = O((m
+ n)k 2 α−2 ) time.
e 3 α−6 ).
3. Computing the SVD of the matrix SU and TVT requires vt2 + tv 2 = O(k
e k requires O(nn(A)) + tv 2 = O(nn(A)) + O(k
e T ZV]
e 3 α−5 ) time.
4. Computation of [U
s

e
5. Computation of the SVD in Step 3 requires (m + n)t2 = O((m
+ n)k 2 α−2 ) time.
To prove part 1, we first invoke Theorem 50. Theorem 50 relates minX,r(X)≤k kAΦXΨA − AkF with
(1 + α)2 kA − [A]k kF as follow.
min kAΦXΨA − AkF ≤ (1 + α)2 kA − [A]k kF .

X,r(X)≤k

(1)

Since V is a matrix whose rows are an orthonormal basis for the row space of ΨA and U is a matrix
whose columns are an orthonormal basis for the column space of AΦ, we have
min
Y,r(Y)≤k

kUXV − AkF ≤

min kAΦXV − AkF ≤

X,r(X)≤k

min kAΦXΨA − AkF .

X,r(X)≤k

(2)

Combining equation (1) and equation (2), we have with probability 1 − 2β over Φ, Ψ ∼ DR ,
min
Y,r(Y)≤k

kUXV − AkF ≤ (1 + α)2 kA − [A]k kF .

(3)

e = argminX,r(X)=k kS(UXVT − A)TkF . Let DA be
Lemma 13. Let U and V be as defined above and X
a distribution that satisfies (α, β)-subspace embedding. Then with probability 1 − O(β) over S, TT ∼ DA ,
e − A)kF ≤ (1 + α)2 kA − [A]k kF .
k(UXV

10

Proof. Set p = k/α, D = U and E = A in the statement of Lemma 8 and v = O(k/α3 log(k/α)). Let
b = argminX,r(X)=k kUXV − AkF and
us restrict our attention to only rank k matrices X and denote by X
e = argminX,r(X)=k kS(UXVT − A)TkF . Then we have with probability 1 − O(β) over S ∼ DA ,
X
b − AkF = (1 ± 3α)−1 kS(UXV
b − A)kF
min kUXV − AkF = kUXV

X,r(X)=k

(4)

b T and E = (SA)T in the statement of Lemma 8, with probability
Substituting D = VT , X = (SUX)
T
1 − O(β) over S, T ∼ DA ,
b − A)kF = (1 ± α)−1 kVT (SUX)
b T − (SA)T )kF
(1 ± 3α)−1 kS(UXV
b T − (SA)T )kF
= (1 ± α)−2 kT(VT (SUX)
b − A)TT kF
= (1 ± α)−2 kS(UXV
≥ (1 ± α)−2 min kS(UXV − A)TT kF
X,r(X)≤k

−2

e − A)TT kF
kS(UXV
e − A)TT kF = (1 ± α)−4 k(UXV
e − A)kF .
= (1 ± α)−3 k(UXV
= (1 ± α)

(5)

Combining equation (5) with equation (3) and equation (4), we have with probability 1 − O(β) over the
coins of Optimal-Space-LRF,
e − A)kF ≤ (1 + α)6 kA − [A]k kF .
k(UXV

(6)

This completes the proof of Lemma 13.
e = argminX,r(X)≤k kS(UXV − A)TT kF .
To finalize the proof of Theorem 12, we need to compute X
e This lemma is a generalization of one of the previous results of
We use the following lemma to compute X.
Clarkson and Woodruff [11].
Lemma 14. Let R be a matrix with orthonormal rows and C be orthonormal columns. Then
min kCXR − FkF = kC[CT FRT ]k R − FkF .

X,r(X)=k

Proof. For any matrix Y of appropriate dimension, we have hF − CCT F, CCT F − CYRi = 0. This is
because F − CCT F = (I − CCT )F lies in space orthogonal to C(CT F − YR). By Theorem 45,
kF − CYRk2F = kF − CCT Fk2F + kCCT F − CYRk2F
= kF − CCT Fk2F + kCT F − YRk2F .

(7)

Again, for any matrix Y of appropriate dimensions, we have hCT FRT R − YR, CT F − CT FRT Ri =
0. This is because CT FRT R − YR = (CT FRT − Y)R lies in the space spanned by R, and CT F −
CT FRT R = CT F(I − RT R) lies in the orthogonal space. By Theorem 45, we have
kCT F − YRk2F = kCT F − CT FRT Rk2F + kCT FRT R − YRk2F

(8)

Since kCT F − CT FRT Rk2F is independent of Y, we just bound the term kCT FRT R − YRk2F . Substituting Y = [CFR]k and using the fact that multiplying R from the right does not change the Frobenius
norm and [CT FRT ]k is the best k-rank approximation to the matrix CT FRT , for all rank-k matrices Z, we
have
kCT FRT R − [CT FRT ]k Rk2F ≤ kCT FRT R − ZRk2F .
11

(9)

Combining equation (9) with equation (8) and Theorem 45, we have
kCT F − [CFR]k Rk2F ≤ kCT F − CT FRT Rk2F + kCT FRT R − ZRk2F
= kCT F − ZRk2F .

(10)

Combining equation (10) with equation (7), the fact that C has orthonormal columns, and Theorem 45, we
have
kF − C[CFR]k Rk2F ≤ kF − CCT Fk2F + kCT F − ZRk2F
= kF − CCT Fk2F + kCCT F − CZRk2F
= kF − CZRk2F .
This completes the proof of Lemma 14.
We now complete the proof of Theorem 12. Recall that SU = Us Σs VsT and TVT = Ut Σt VtT .
e s, R = V
e T and F = Z = SATT , we get
Invoking Lemma 14 with C = U
t
e T ZV
e t ]k = [U
e T SATT V
e t ]k = argmin kU
e s XV
e T − SATT kF
[U
s
s
t
X,r(X)≤k

e=
⇒X

e sΣ
e † [U
e T ZV
e t ]k Σ
e †U
eT
V
s
s
t t

= argmin kS(UXV − A)TT kF .

(11)

X,r(X)≤k

Substituting equation (11) in equation (6), and adjusting the value of α by a constant, we have the final
result.

4

Space-Optimal Private Algorithm for Low-rank Factorization Under Priv1

In this section, we convert the algorithm presented in the last section to a differentially private algorithm.

b Φ,
b Yr = ΨA,
b and Z = SAT
b T for A
b = A σmin Im ; else
When m ≤ n, we maintain sketches Yc = A

b Φ)
b T , Yc = (ΨA)
b T , and Z = (SAT
b T )T for A
b = AT σmin In . In this section,
we maintain Yr = (A
we consider Priv1 as the granularity of privacy, a generalization of previously studied privacy levels [6, 28,
34, 33, 63]. Figure 2 give the description of our algorithm. Our main result in this section is as follows.
Theorem 15.
pLet m, n, k ∈ N and α, β, ε, δ be the input parameters. Let s = max{m, n} and σmin =
16 log(1/δ) t(1 + α)(1 − α)−1 ln(1/δ)/ε. Given an m×n matrix A in a turnstile update model, PrivateSpace-Optimal-LRF, described in Figure 2, outputs a factorization UU0 , Σ0 , VT V0 such that
2 v 2 /8

1. With probability 1 − O(δ) − 2−`

over the random coins of Private-Space-Optimal-LRF,
p
√
kA − Mk kF ≤ (1 + α)kA − [A]k kF + O(σmin m + n + (ρ2 v` + ρ1 k(m + n)/(1 ± α)).

2. Private-Space-Optimal-LRF is (3ε, 3δ)-differentially private.
3. The space used by Private-Space-Optimal-LRF is O((m + n)(k + 1/α)α−1 log k log(1/δ)).
e
4. The initialization time of the algorithm is O(m+n),
the update time is O(s2 (k+1/α)α−1 ), and the total time to perform the factorization is O(nn(A) log(1/δ))+O((nk 2 α−2 +mk 2 α−2 +k 3 α−4 ) log(1/δ)).
Part 4 and 3 of Theorem 15 follows as in the proof of Theorem 12 by setting the values of t and v. Note
that here the update time also requires multiplication by a random Gaussian matrix. In Section 4.1, we prove
part 2 of Theorem 15. Then in Section 4.2, we prove part 1 of Theorem 15.
12

Initialization. Let t = O(max{kα−1 , α−2 } log(k) log(1/δ)), v = O(max{kα−2 , α−4 } log k log(1/δ)), and u =
u×t
(m+n)×u
min {m, n}. Sample Ω ∼ N
, Ψ ∈pRt×u such that ΦT ∼ DR and Ψ ∼ DR
p(0, 1) . Let Φ ∈ R
satisfies Lemma 7. Let ρ1 = (1 + α) ln(1/δ)/ε and ρ2 = (1 + α) ln(1/δ)/ε. Let S ∈ Rv×u , T ∈ Rv×(m+n)
such that S ∼ DA and TT ∼ DA satisfies Lemma 8. Sample
N1 ∼ N (0, ρ21 )t×(m+n) and N2 ∼ N (0, ρ22 )v×v .
p
b = t−1 ΦΩ ∈ R(m+n)×t . Set σmin = 16 log(1/δ) t(1 + α)(1 − α)−1 ln(1/δ)/ε.
Define Φ

b = 0m×n σmin Im . Compute Yc = A
b Φ,
b Y0 = ΨA,
b and Z0 = SAT
b T.
Case 1: When u = m, set A
r

Update rule. When (iτ , jτ , Aτ ), where (iτ , jτ ) ∈ [m]×[n], is streamed, update the matrices by the following
b j ,j for all 1 ≤ j ≤ t, (ii) (Y0 )i,j = (Y0 )i,j + Aτ Ψi,j for all
rule: (i) (Yc )iτ ,j = (Yc )iτ ,j + Aτ Φ
r
r
τ
τ
τ
τ
0
0
1 ≤ j ≤ t, and (iii) Zi,j = Zi,j + Si,iτ Aτ Tj,jτ for all 1 ≤ i, j ≤ v.

Computing the factorization. Once the matrix is streamed, we follow the following steps.
b + N1 , and Z = Z0 + N2 = SAT
b T + N2 .
1. Compute Yr = Yr0 + N1 = ΨA
m×t
2. Compute a matrix U ∈ R
whose columns are an orthonormal basis for the column space of Yc and
matrix V ∈ Rt×(m+n) whose rows are an orthonormal basis for the row space of Yr .
e sΣ
e sV
e T . Compute a SVD of VTT ∈ Rt×v . Let it be
3. Compute a SVD of SU ∈ Rv×t . Let it be U
s
T
e tΣ
e tV
e .
U
t
e sΣ
e † [U
e T ZV
e t ]k Σ
e †U
e T ∈ Rt×t . Let it is be U0 Σ0 V0T .
4. Compute a SVD of V
s

s

t

t

5. Output the matrix UU0 comprising of left singular vectors, diagonal matrix Σ0 and the matrix VT V0
comprising of right-singular vectors. Denote by Mk = UU0 Σ(VT V0 )T .

b = 0n×m σmin In . Compute Yr = (A
b T , and Z0 = (SAT
b T )T .
b Φ)
b T , Y0 = (ΨA)
Case 2: When u = n, set A
c

Update rule. When (iτ , jτ , Aτ ), where (iτ , jτ ) ∈ [m]×[n], is streamed, update the matrices by the following
b j ,i for all
rule: (i) (Yc0 )j,iτ = (Yc0 )j,iτ + Aτ Ψj,jτ for all 1 ≤ j ≤ t, (ii) (Yr )jτ ,i = (Yr )jτ ,i + Aτ Φ
τ
0
0
1 ≤ j ≤ t, and (iii) Zi,j = Zi,j + Ti,iτ Aτ Sj,jτ for all 1 ≤ i, j ≤ v.

Computing the factorization. Once the matrix is streamed, we follow the following steps.
b + N1 )T and Z = (Z0 + N2 )T = (SAT
b T + N2 )T .
1. Compute Yc = (Yc0 + N1 )T = (ΨA
2. Compute a matrix U ∈ R(m+n)×t whose columns are an orthonormal basis for the column space of Yc
and matrix V ∈ Rt×n whose rows are an orthonormal basis for the row space of Yr .
e tΣ
e tV
e T . Compute a SVD of VST ∈ Rt×v . Let it be
3. Compute a SVD of TU ∈ Rv×t . Let it be U
t
e sΣ
e sV
e T.
U
s
e T ZV
e s ]k Σ
e †U
e T ∈ Rt×t . Let it is be U0 Σ0 V0T .
e tΣ
e † [U
4. Compute a SVD of V
t

t

s

s

5. Output the matrix UU0 comprising of left singular vectors, diagonal matrix Σ0 and the matrix VT V0
comprising of right-singular vectors. Denote by Mk = UU0 Σ(VT V0 )T .
Figure 2: Space-efficient Private Low-rank Approximation Under Priv1 (Private-Space-Optimal-LRF)

4.1

Proof of Part 2 of Theorem 15

Lemma 16. If σmin and ρ be as in Theorem 15, then the algorithm presented in Figure 2, Private-SpaceOptimal-LRF, is (3ε, 3δ)-differentially private.
b
Proof. We prove the lemma when m ≤ n. The case for m ≥ n is analogous after inverting the roles of Φ
0
0
T
0
b
b
and Ψ. Let A and A be two neighboring matrices, i.e., E = A − A = uv . Then
 A and A , constructed
b0 = A
b+ E 0 .
by Optimal-Space-Private-LRF, has the following property: A
p
p
Claim 17. If ρ1 = (1 + α) ln(1/δ)/ε and ρ2 = (1 + α) ln(1/δ)/ε, then publishing Yr and Z preserves(2ε, 2δ)differential privacy.
13

Proof. We use the second claims of Lemma 7 and Lemma 8, i.e., kSDk2F = (1 ± α)kDk2F and kΨDk2F =
(1 ± α)kDk2F for all D, where S ∼ DA and
∼ DR . Let A and A0be two neighboring matrices such
 Ψ
0
T
T
that E = A − A = uv . Then kS E 0 T k2F ≤ (1 + α)k E 0 TT k2F = (1 + α)2 . Publishing Z
b T and N2
preserves (ε, δ)-differential privacy follows from considering the vector form of the matrix SAT
and applying Theorem 11. Similarly, we use Theorem 11 and the fact that, for any matrix C of appropriate
b + N1 preserves differential privacy.
dimension, kΨCk2 = (1 ± α)kCk2F , to prove that publishing ΨA
We next prove that Yc is (ε, δ)-differentially private. This would complete the proof of Lemma 16 as
the lemma would follow by combining Lemma 9 and Theorem 10. One of the key ideas behind the proof is
an application of one of the results of Sarlos [58]. Sarlos [58] observed that since any distribution satisfying
b has a full-row rank and Φ satisfies (α, δ)-JLP, then with probability 1 − δ, the
the JLP is an isometry, if A
b
b
singular values of AΦ are within a multiplicative factor
(1 ± α)1/2 of A.

m
0
T
0
b −A
b = ub
b = v 0 . Then A
Let A − A = E = uv and let v
vT . Since ΦT is sampled from DR ,
we have kΦT Wk2F = (1 + α)kWk2F for any matrix W with probability 1 − δ (second claim of Lemma 7).
b = (1 + α)1/2 v
e for some unit vector v
e . That is, uvT Φ = (1 + α)1/2 ue
Therefore, ΦT v
vT for some unit
b
e .We now show that AΦΩ
vectors u and v
1 preserves privacy. We prove that each row of the published
matrix preserves (ε0 , δ0 )-differential privacy for some appropriate ε0 , δ0 , and then invoke Theorem 10 to
prove that the published matrix preserves (ε, δ)-differential privacy.
The proof of privacy follows the same line as the proof of Blocki et al. [6]; however, we need to take
care of two things. First, the definition of neighboring matrices considered in this paper is different from
that of Blocki et al. [6]. To recall, Blocki et al. [6] considered two matrices neighboring if they differ in at
most one row by a unit norm. In our case, we consider two matrices are neighboring if they have the form
b and not to A,
b as in Blocki et
uvT for unit vectors u, v. Secondly, we multiply the Gaussian matrix to AΦ
al. [6]. However, this is not a problem because Φ satisfies (α, δ)-JLP because of the choice of t. Since the
b and AΦ
b are the same with probability 1 − δ, the singular values of AΦ
b are within a multiplicative
rank of A
1/2
factor of (1 ± α)
of the singular values of Φ due to Sarlos [58]. Therefore, our proof goes through if
b appropriately. In this sense, we generalize the privacy result of Blocki et
we scale the singular values of A
al. [6].


b = A σmin Im and by A
b 0 = A0 σmin Im , where A − A0 = uvT . Then A
b0 − A
b =
Denote by A

T
T
T
0
b and U
e CΣ
e CV
e be the SVD of C
e =A
b Φ. From above
uv
0 . Let UC ΣC VC be the SVD of C = AΦ
C
0
T
1/2
T
e = (1 + α) u
ev
e for some unit vectors u
e and v
e.
discussion, we know that if A − A = uv , then C − C
e and v for v
e.
For notational brevity, in what follows we write u for u
e is a full rank matrix because of the construction; therefore CCT is a full
Note that both C and C
dimensional m × m matrix. This implies that the affine transformation of the multi-variate Gaussian is
well-defined (both the covariance (CCT )−1 has full rank and ∆(CCT ) is non-zero). That is, the PDF of
e is just a linear transformation of N (0, Im×m ). Let
the distributions of the rows, corresponding to C and C,
t
y ∼ N (0, 1) .
1
1
T −1 T
e(− 2 x(CC ) x )
PDFCY (x) = p
d
T
(2π) ∆(CC )
1
1
e e T −1 T
PDFCY
e(− 2 x(CC ) x )
e (x) = q
eC
e T)
(2π)d ∆(C

We prove the result for a row of the published matrix; the theorem follows from Theorem 10. Let
ε
eC
e T ). It is
and δ0 = δ/2r, Let x be sampled either from N (0, CCT ) or N (0, C
ε0 = √
4r ln(1/δ) log(1/δ)

14

straightforward to see that the combination of Claim 18 and 19 proves differential privacy for a row of
published matrix. The lemma then follows by an application of Theorem 10 and our choice of ε0 and δ0 .
Claim 18. Let C and ε0 be as defined above. Then
s
∆(CCT )
e−ε0 ≤
≤ eε0 .
eC
e T)
∆(C
T
Proof.
Q 2 The claim follows simply as in [6] after a slight modification. More concretely, we have ∆(CC )e=
e1 ≥ · · · ≥ σ
em ≥ σmin (C)
i σi , where σ1 ≥ · · · ≥ σm ≥ σmin (C) are the singular values of C. Let σ
√
e
be its singular value for C. There is only one singular value of E and it is 1 + α. This is because
EET = (1 + α)vvT . To finish the proof of this claim, we use Theorem 46.
e and C
e − C are the same, Lidskii’s theorem (Theorem 46) gives
values of C − C
√
P Since the singular
ei ) ≤ 1 + α. Therefore, with probability 1 − δ,
i (σi − σ
v
!

u Y
Y 
X
u
σ
ei2
σ
ei − σi
ε
t
p
1+
≤ exp
=
(e
σi − σi ) ≤ eε0 /2 .
σi
σi2
32(1
+
α)
t
log(2/δ)
log(t/δ)
i
i:e
σ ≥σ
i:e
σ ≥σ
i

i

i

i

The last inequality holds because Φ ∼ DR satisfies (α, δ)-JLP due to the choice of t (second claim
of Lemma 7). Since C and A have same rank, this implies, due to a result by Sarlos [58], that all the
b (Lemma 48). In other words,
singular values of C are within a (1 ± α)1/2 multiplicative factor of A
1/2
σmin (C) ≥ (1 − α) σmin . The case for all i ∈ [m] when σ
ei ≤ σi follows similarly as the singular values
of E and −E are the same. This completes the proof of Claim 18.
e
Claim 19. Let C, ε0 , and δ0 be as defined earlier. Let y ∼ N (0, 1). If x is sampled either from Cy or Cy,
then we have
h
i
eC
e T )−1 x ≤ ε0 ≥ 1 − δ0 .
Pr xT (CCT )−1 x − xT (C
e is analogous. Let
Proof. Without any loss of generality, we can assume x = Cy. The case for x = Cy
T
n
e = vu . Note that E[(Ω)i,j ] = 0 and COV((Ω)i,j ) = 1 if and only if i = j. Then
C−C
eC
e T )−1 x = xT (CCT )−1 (C
eC
e T )(C
eC
e T )−1 x − xT (C
eC
e T )−1 x
xT (CCT )−1 x − xT (C
e C)
e −1 x − xT (C
e C)
e −1 x
= xT (CCT )−1 (C + uvT )(CT + vuT )(C
i
h
e T )(C
eC
e T )−1 x.
= xT (CCT )−1 (CuvT + vuT C
T and C
e =U
e CΣ
e CV
e T , we have
Using the singular value decomposition of C = UC ΣC VC
C


 


e CΣ
e −2 U
e T )x + xT (UC Σ−2 UT )v uT (V
e CΣ
e −1 U
e T )x
xT (UC Σ−1 VT )u vT (U
C

C

C

C

C

C

C

C

Since x ∼ Cy, where y ∼ N (0, 1)t , we can write the above expression as τ1 τ2 + τ3 τ4 , where




T
e CΣ
e −2 U
e T )Cy
τ1 = yT CT (UC Σ−1
τ2 = vT (U
C
C VC )u
C




T
T e e −1 e T
τ3 = yT CT (UC Σ−2
U
)v
τ
=
u
(
V
Σ
U
)Cy
.
4
C C
C
C
C
e C k2 , kΣC k2 ≥ σmin (C), plugging in the SVD of C and C − C
e = vuT , and that every
Now since kΣ
term τi in the above expression is a linear combination of a Gaussian, i.e., each term is distributed as per

15

N (0, kτi k2 ), we calculate kτi k as below.
−1 T
k(VC ΣC UT
C )(UC ΣC VC )uk2 ≤ kuk2 ≤ 1,
−2 T
−1
k(VC ΣC UT
C )(UC ΣC UC )vk2 ≤ kΣC k2 ≤

1
,
σmin (C)

e CΣ
e −2 U
e T )(U
e CΣ
e CV
e T − vuT )k2
kvT (U
C
C
C
e CΣ
e −2 U
e T )U
e CΣ
e CU
e T k2 + kvT (U
e CΣ
e −2 U
e T )vuT k2 ≤
≤ kvT (U
C
C
C
C
C

1
1
,
+ 2
σmin (C) σmin
(C)

e CΣ
e −1 U
e T )(U
e CΣ
e CV
e T − vuT )k2
kuT (V
C
C
C
e CΣ
e −1 U
e T )(U
e CΣ
e CV
e T k2 + kuT (V
e CΣ
e −1 U
e T )vk2 ≤ 1 +
≤ kuT (V
C
C
C
C
C

1
.
σmin (C)

Using the concentration bound on the Gaussian distribution, each term, τ1 , τ2 , τ3 , and τ4 , is less than
kτi k ln(4/δ0 ) with probability 1 − δ0 /2. The second claim follows from the following inequality:




1
1
T
T −1
T e T e −1
Pr x (CC ) x − x (C C) x ≤ 2
+ 2
ln(4/δ0 ) ≤ ε0 ≥ 1 − δ0 ,
σmin (C) σmin
(C)
where the second inequality follows from the choice of σmin and the fact that σmin (C) ≥ (1−α)1/2 σmin .
Combining Claims 18 and 19, Lemma 16 follows.

4.2

Proof of Part 1 of Theorem 15

In what follows, we analyze the case when m ≤ n. The case when n ≤ m follows analogously due to the
symmetry of Private-Space-Optimal-LRF. First note that appending
A with an all zero matrix 0m×m has

no effect on its k-rank approximation, i.e., we can analyze A 0 . We break our proof in three main steps.

b F by kMk − A 0 kF up to an additive term.
(i) Lower bound kMk − Ak
b F and kA
b − [A]
b k kF .
(ii) Relate kMk − Ak
b − [A]
b k kF by a term linear in kA − [A]k kF up to an additive factor.
(iii) Upper bound kA
Part 1 of Theorem 15 follows by fitting together the above three bounds.
b F by kMk − AkF and a small additive
Performing step (i). We start by proving a bound on kMk − Ak
term. The following lemma provides such a bound.

b = A σmin Im for σmin defined in Theorem 15.
Lemma 20. Let A be an m × n input matrix, and let A

Denote by Mk := UU0 Σ0 (VV0 )T the output of Private-Optimal-Space-LRF. Then kMk − A 0 kF ≤
b F + σmin √m.
kMk − Ak
Proof. The lemma is immediate from the following.



b F,
kMk − A 0 kF − σmin kIm kF ≤ kMk − A 0 − 0 σmin I kF = kMk − Ak
where the first inequality follows from the sub-additivity of norms.

16

Performing step (ii). This is the most involved part of the proof and uses multiple lemmas as follows.

b = A σmin I and denote by Mk := UU0 Σ0 (VV0 )T . Let Φ
b = ΦΩ. Then with
Lemma 21. Let A
probability 1 − O(δ) over the random coins of the algorithm Private-Space-Optimal-LRF,
b F ≤ (1 + α)kA
b − [A]
b k kF + kA
b Φ([
b A]
b k Φ)
b † (ΨA
b Φ([
b A]
b k Φ)
b † )† N1 kF + 2kS† N(TT )† kF .
kMk − Ak
† N(T† )T and Φ
b
b = t−1 ΩΦ. We first use the relation between minX,r(X)≤k kA
b ΦXΨ
b
b
Proof. Let B = A+S
A−
b and (1 + α)kA
b − [A]
b k kF shown by Boutsidis et al. [8]. Using the Fact 6 and Lemma 7, if we set A = A
b
Ak
T
b
in equation (39), we have with probability 1 − 2δ over Φ , Ψ ∼ DR ,

b Φ([
b A]
b k Φ)
b † (ΨA
b Φ([
b A]
b k Φ)
b † )† ΨA
b − Ak
b F ≤ (1 + α)2 kA
b − [A]
b k kF .
kA
b k Φ)
b † (ΨA
b Φ([
b A]
b k Φ)
b † )† .
Consider the optimization problem: minX,r(X)≤k kYc XYr −BkF . Define Pk := ([A]
Since Pk is a rank-k matrix, we have
b + S† N(T† )T )kF
min kYc XYr − BkF ≤ kYc Pk Yr − BkF = kYc Pk Yr − (A

X,r(X)≤k

b F + kS† N(T† )T kF
≤ kYc Pk Yr − Ak
b ΦP
b k (ΨA
b + N1 ) − Ak
b F + kS† N(T† )T kF
= kA
b ΦP
b k ΨA
b − Ak
b F + kS† N2 (T† )T kF + kA
b ΦP
b k N1 kF
≤ kA
b ΦP
b k N1 kF
b − [A]
b k kF + kS† N2 (T† )T kF + kA
≤ (1 + α)2 kA

(12)

b ΦP
b k N1 . We have an upper bound on minX,r(X)≤k kYc XYr − BkF in the terms of (1 +
Let S2 = A
b − [A]
b k kF and some additive terms. Since V is a matrix whose rows are an orthonormal basis for the
α)kA
row space of Yr and U is a matrix whose columns are an orthonormal basis for the column space of Yc ,
we have
min
Y,r(Y)≤k

kUXV − BkF ≤

min kYc XV − BkF ≤

min kYc XYr − BkF .

(13)

b − [A]
b k kF + kS† N2 (T† )T kF + kS2 kF .
kUXV − BkF ≤ (1 + α)2 kA

(14)

X,r(X)≤k

X,r(X)≤k

Combining equation (12) and equation (13), we have
min
Y,r(Y)≤k

Claim 22. Let U, V, B, A, S, T and N2 be as above. Let DA be a distribution that satisfies (α, β)-subspace
e = argminX,r(X)=k kS(UX − B)kF , then with probability 1 − O(δ) over S, TT ∼ DA ,
embedding. Let X
b − [A]
b k kF + kS† N2 (T† )T kF + kS2 kF .
e − B)kF ≤ (1 + α)6 kA
k(UXV
Proof. Set p = t, D = U and E = B in the statement of Lemma 8. Let us restrict our attention to only
b = argminX,r(X)=k kUXV − BkF and X
e = argminX,r(X)=k kS(UXV −
rank k matrices X and denote by X
T
B)T kF . Then we have with probability 1 − 3δ over S ∼ DA ,
b − BkF = (1 ± α)−1 kS(UXV
b − B)kF .
min kUXV − BkF = kUXV

X,r(X)=k

17

(15)

b T and E = (SB)T in the statement of Lemma 8, with probability 1−4δ,
Substituting D = VT , X = (SUX)
b − B)kF = (1 ± α)−1 kVT (SUX)
b T − (SB)T )kF
(1 ± α)−1 kS(UXV
b T − (SB)T )kF
= (1 ± α)−2 kT(VT (SUX)
b − B)TT kF
= (1 ± α)−2 kS(UXV
≥ (1 ± α)−2 min kS(UXV − B)TT kF
X,r(X)

−2

= (1 ± α)

e − B)TT kF = (1 ± α)−4 k(UXV
e − B)kF .
kS(UXV

(16)

Combining equation (16) with equation (14) and equation (15), we have with probability 1 − O(δ) over
the random coins of Private-Optimal-Space-LRF,
b − [A]
b k kF + kS† N2 (T† )T kF + kS2 kF .
e − B)kF ≤ (1 + α)6 kA
k(UXV

(17)

This completes the proof of Claim 22.
e = argminX,r(X)≤k kS(UXV − B)TT kF . Recall SU =
To finalize the proof, we need to compute X
e s, R = V
e T and F = Z = SAT
b T + N,
Us Σs VsT and TVT = Ut Σt VtT . Invoking Lemma 14 with C = U
t
we get
e T ZV
e t ]k = [U
e T SBTT V
e t ]k = argmin kU
e s XV
e T − SBTT kF
[U
s
s
t
X,r(X)≤k

e=
⇒X

e sΣ
e † [U
e T ZV
e t ]k Σ
e †U
eT
V
s
s
t t

= argmin kS(UXV − B)TT kF .

(18)

X,r(X)≤k

0 0 T
e sΣ
e †s [U
e T ZV
e t ]k Σ
e †U
eT
e =V
Recall, X
s
t t = U Σ V . Substituting equation (18) in equation (17) and the fact
b + S† N2 (T† )T , we have
that B = A

b F − kS† N2 (TT )† kF ≤ kUU0 Σ0 (VT V0 )T − BkF
kUU0 Σ0 (VT V0 )T − Ak
b − [A]
b k kF + kS† N2 (TT )† kF + kS2 kF
≤ (1 + α)6 kA
b F ≤ (1 + α)6 kA
b − [A]
b k kF + 2kS† N2 (TT )† kF + kS2 kF .
⇒ kUU0 Σ0 (VT V0 )T − Ak
Scaling the value of α by a constant completes the proof of Lemma 21.
To compute the additive error, we need to bound kS† N2 (TT )† kF and kS2 kF . This is done by the
following two lemmas.
Claim 23. Let DR be a distribution that satisfies (α, β)-subspace embedding for generalized
√ regression. Let
b ∼ DR , kS2 kF = ρ(1 ± α)−1 kn.
S2 be as defined above. Then with probability 1 − δ over Φ
b k Φ)† . G is an t × k matrix. When α ≤ 1, G is a full column rank. This
Proof. Let G = ΨAΦ([A]
b with orthonormal columns such that GG† = U
bU
b T . Therefore,
implies that there exist a t × k matrix U
bU
b T N1 . From the second claim of Lemma 7 and the choice of the parameter t,
ΨS2 = GG† N2 = U
2
−1
b
b
b bT
kS2 kF = (1 ± α) kUUT N2 k2F . Since every entries of N2 are
p picked i.i.d. and UU is an orthonormal
projection onto a k-dimensional subspace, we have kS2 kF = ρ kn/(1 ± α).
Claim 24. Let S, T ∼ DA . Then for any matrix N2 of appropriate dimension, kS† N2 (TT )† kF = kN2 kF .
Proof. The proof follows by two applications of Lemma 49.

18

Initiialization. Set t = O(max{kα−1 , α−2 } log(1/δ)), v = O(max{kα−2 , α−4 } log(1/δ)). Sample Φ ∈ Rm×t
from DR as in Lemma 7 and S ∈ Rv×n from DR as in Lemma 8. Sample N1 ∼ N (0, ρ2 )m×t , N2 ∼ N (0, ρ2 )v×n .
Initialize an all zero m × t matrix Y0 and an all zero v × n matrix Z0 .

Update rule. Suppose at time τ , the stream is (iτ , jτ , Aτ ), where (iτ , jτ ) ∈ [m] × [n]. Update the matrices by the
following rule: Yi0τ ,j = Yi0τ ,j + Aτ Φjτ ,j for all 1 ≤ j ≤ t and (Z)0i,jτ = (Z)0i,jτ + Aτ Si,jτ for all 1 ≤ j ≤ v.

Computing the factorization. Once the matrix is streamed, we follow the following steps.
1. Compute Y = Y0 + N1 and Z = Z0 + N2 .
2. Compute a matrix U ∈ Rm×t whose columns are an orthonormal basis for the column space of Y.
eΣ
eV
e T.
3. Compute the singular value decomposition of SU ∈ Rv×t . Let it be U
eΣ
e † [U
e T Z]k . Let it be U0 Σ0 V0T .
4. Compute the singular value decomposition of V
5. Output UU0 , Σ0 and V0 . Let Mk = UU0 Σ0 V0T .
Figure 3: Private Low-rank Approximation Under Priv2 (Private-Frobenius-LRF)

Using Lemma 47, we know that kN2 kF = O(ρv) with probability 99/100. If we instead use the
2 2
concentration bound of χ2 -distribution, then kN2 kF = O(ρv`) with probability 1 − 2−` v /8 .
b − [A]
b k kF . For
Performing step (iii). In order to complete the proof, we compute an upper bound on kA
this, we need the Weyl’s perturbation theorem:
Theorem 25. For any m × n matrices P, Q, we have |σi (P + Q) − σi (P)| ≤ kQk2 , where σi (·) denotes
the i-th singular value and kQk2 is the spectral norm of the matrix Q.
b Let σ1 , · · · , σd be the singular values of A and
Lemma 26. Let d be the maximum of the rank of A and A.
0
0
0
b
σ1 , · · · , σd be the singular values of A. Then |σi − σi | ≤ σ for all 1 ≤ i ≤ d.

b = A 0 +
Proof. The lemma follows from the basic application of Theorem 25. We can write A

0 σmin Im . The lemma follows since, by construction, all the singular values of 0 σmin Im are σmin .
P
2
02
2
b − [A]
b k k2 ≤ P
Since kA
i>k σi , combining Lemma 20, Lemma 21,
i>k σi and kA − Ak kF ≤
F
Claim 23, Claim 24, Lemma 26, and Lemma 47, we have the final utility bound.
Lemma 27. Let ρ and σmin be as defined in Theorem 15. With probability 99/100 over the coins of the
algorithm Private-Optimal-Space-LRF, the output of Private-Optimal-Space-LRF satisfies
√

√
k A 0 − Mk kF ≤ (1 + α)kA − [A]k kF + O(σmin m + ρ1 (1 ± α)−1 kn + ρ2 v).
The result follows by setting the values of ρ and σmin .

5

Efficient-update and Optimal-error Differentially-private LRF Under Priv2

In the previous section, we gave an space-optimal (when k ≥ 1/α) and optimal additive error algorithm for
LRF under Priv1 . In this section, we show a differentially private algorithm that outputs a k-rank factorization of an m × n matrix under an even stronger level of privacy, Priv2 . Our idea is to show that the algorithm
of Clarkson and Woodruff [13] can be made to work in the turnstile update model while incurring optimal
additive error. The main result of this section is the following theorem.
Theorem 28. Let m, n ∈ N and α, ε, δ be the input parameters. Let k be the desired rank of the factorization
and let s = max{m, n}. Given a private input matrix A ∈ Rm×n streamed in a turnstile model, the

19

e Σ,
e V
e outputted by the algorithm, Private-Frobenius-LRF, presented in Figure 3 satisfies
factorization U,
the following properties:
1. Private-Frobenius-LRF outputs a low rank factorization such that, with probability 99/100 over the
coins of the algorithm,
s
!

! p
√
log(1/δ)
1
n(1 + α)
kA−Mk kF ≤ (1+α)kA−[A]k kF +O
(1 + α) km +
k+
,
α3
α
ε
eΣ
eV
e T.
where Mk := U
2. Private-Frobenius-LRF is (ε, δ)-differentially private.
3. The space used by Private-Frobenius-LRF is O((m + nα−2 )kα−2 log k log(1/δ)).
2 α−3 +
e
4. The update time of Private-Frobenius-LRF is O(log s). It requires O(nn(A)) + O(nk
2
−5
3
−6
mk α + k α ) to compute LRF, where nn(A) denotes the sparsity of the matrix A.

The space required by the algorithm is the space required to store Y and Z, which is mt2 + nv 2 =
O((m + nα−2 )kα−2 log k log(1/δ)). This proves part 3 of Theorem 28. For the update time in part 3
of Theorem 12, note that Φ updates in input-sparsity time, which is constant, plus O(log(m + n)). The
same is true for the update time of Z. For the running time of part 4 of Theorem 28, we have the following:
1. Computing the sketch Y requires O(nn(A))+mt2 time and computing the sketch Z requires O(nn(A))+
−1 (k + α−2 )2 ) and O(nn(A)) +
e
nv 2 . Therefore, computing Y and Z requires O(nn(A)) + O(mα
−3
−2
2
e
O(nα
(k + α ) ), respectively.
2 α−4 ) time.
e
2. Computing the orthonormal basis U requires mt2 = O(mk
e 3 α7 ).
3. Computing the SVD of the matrix SU requires vt2 = O(k
2 α−6 ) time.
e T Z]k requires nv 2 = O(nk
e
4. Computation of [U
2 α−4 ) time.
e
5. Computation of the SVD in Step 4 requires nt2 = O(nk

The following lemma proves Part 2 of Theorem 28.
√
(1+α) ln(1/δ)
Lemma 29. If ρ =
, then Private-Frobenius-LRF is (ε, δ)-differentially private.
ε
Proof. To prove this lemma, we use the second claims of Lemma 7 and Lemma 8, i.e., for all D, kSDk2F =
(1 ± α)kDk2F for S ∼ DA and kΦDk2F = (1 ± α)kDk2F for Φ ∼ DR . Let A and A0 be two neighboring
matrices such that E = A − A0 has Frobenius norm 1. Then kSEk2F ≤ (1 + α)kEk2F = 1 + α. Publishing
Z preserves (ε, δ)-differential privacy follows from considering the vector form of the matrix SA and N2
and Theorem 11. Similarly, we use the fact that, for any matrix C of appropriate dimension, kΦCk2 =
(1 ± α)kCk2F , to prove that publishing AΦ + N1 preserves differential privacy. The lemma follows by
applying Lemma 9 and Theorem 10.
We prove part 1 in two stages by decoupling the effect of the noise matrices N1 and N2 . In the first
step, we assume that the noise N1 is not introduced and then analyze the algorithm. Later, in Section 5.2,
we perform the analysis of the algorithm as presented in Figure 3.

20

5.1

Simplication Step

We first prove the result without the effect of using N1 . That is, in the following analysis, we consider U0 ,
a matrix whose columns are formed by an orthonormal basis of the column-space of AΦ instead of U, a
matrix whose columns are formed by an orthonormal basis of the column-space of AΦ + N1 . In this case,
eΣ
e † [U
e T Z]k is a good approximation of A. We show the following
we show that U0 V
eΣ
e † [U
e T Z]k , where U0 is as defined above and rest of the terms as defined
Theorem 30. Let M0k := U0 V
in Figure 3. Then with probability 1 − O(δ) over Φ ∼ DR and S ∼ DA ,
kM0k − AkF ≤ (1 + α)kA − [A]k kF + 2kS† N2 kF .
Proof. We prove this lemma using few claims.
Lemma 31. Let A be the input matrix. Let Φ ∼ DR , S ∼ DA be as in Figure 3 . Let B = A + S† N2 for
N2 defined as in Figure 3. Then
min kAΦX − BkF ≤ (1 + α)kA − [A]k kF + kS† N2 kF .

X,r(X)≤k

T
Proof. Set r = k, P = [A]T
k , and Q = A in the statement of Lemma 7. Then using Lemma 7 with
t = O(k/α log(r/α)), we have with probability 1 − β over Φ ∼ DR ,
T
0
T
T
0
T
T
k[A]T
k X − A kF ≤ (1 + α) min k[A]k − AkF , where X = argmin kΦ ([A]k X − A )kF .
X

X

Taking the transpose and the fact that the Frobenius norm is preserved under transpose and X0 = (([A]k Φ)T )† (AΦ)T ,
we have with probability 1 − δ over Φ ∼ DR ,
kAΦ([A]k Φ)† [A]k − AkF ≤ (1 + α)kA − [A]k kF .

(19)

Since ([A]k Φ)† [A]k has rank at most k, we have with probability 1 − δ over Φ ∼ DR ,
min kAΦX − BkF ≤ kAΦ([A]k Φ)† [A]k − BkF

X,r(X)≤k

≤ kAΦ([A]k Φ)† [A]k − AkF + kS† N2 kF

(20)

Combining equation (19) and equation (20), with probability 1 − δ over Φ ∼ DR ,
min kAΦX − BkF ≤ (1 + α)kA − [A]k kF + kS† N2 kF ,

X,r(X)≤k

(21)

which is what was required.
Till now, we have related minX,r(X)≤k kAΦX − Bk with (1 + α)kA − [A]k kF and kS† N2 kF . Since
U0 is a matrix whose columns are an orthonormal basis for the column space of AΦ, we have
min kU0 X − BkF ≤

X,r(X)≤k

min kAΦX − BkF .

X,r(X)≤k

(22)

Using equation (22) in Lemma 31, we have
min kU0 X − BkF ≤ (1 + α)kA − [A]k kF + kS† N2 kF .

X,r(X)≤k

(23)

Lemma 32. Let U0 , B, A, S, and N2 be as in Lemma 31. Let DA be a distribution that satisfies (α, β)e = argminX,r(X)=k kS(UX − B)kF , then with probability 1 − 2δ over S ∼ DA ,
subspace embedding. Let X
e − B)kF ≤ (1 + α)3 kA − [A]k kF + kS† N2 kF .
k(U0 X

21

Proof. Set p = k/α, D = U0 , E = B, and v = O(k/α3 log(k/α) log(1/δ)) in the statement of Lemma 8.
b = argminX,r(X)=k kU0 X − BkF and
Let us restrict our attention to rank k matrices X and denote by X
e = argminX,r(X)=k kS(UX − B)kF . Then we have with probability 1 − 2δ over S ∼ DA ,
X
b − BkF = (1 ± α)−1 kS(U0 X
b − B)kF
min kU0 X − BkF = kU0 X

X,r(X)=k

≥ (1 ± α)−1 min kS(U0 X − B)kF
X,r(X)

e − B)kF = (1 ± α)−2 k(U0 X
e − B)kF .
= (1 ± α)−1 kS(U0 X

(24)

Combining equation (24) with equation (23), we have
e − B)kF ≤ (1 + α)3 kA − [A]k kF + kS† N2 kF .
k(U0 X

(25)

This completes the proof.
e = argminX,r(X)≤k kS(U0 X − B)kF and
To finalize the proof of Theorem 30, we need to compute X
e − B)kF . For this, we use the following result by Clarkson and Woodruff [11].
lower bound k(U0 X
Lemma 33. [11, Theorem 4.3]) Let O be an orthonormal matrix and Z ∈ Rm×v .Then
[OT Z]k = argmin kOX − ZkF .
X,r(X)≤k

e and Z = SB. We get [U
e T SB]k = argminX,r(X)≤k kUX
e − SBkF .
Invoking Lemma 33 with O = U
This implies that
eΣ
e † [U
e T SB]k = argmin kS(U0 X − B)kF .
e=V
X

(26)

X,r(X)≤k

Using equation (26) in equation (25) and the fact that B = A + S† N2 ,by appropriate scaling of α, we
have the final result.
eΣ
e † [U
e T Z]k − AkF − kS† N2 kF ≤ kU0 V
eΣ
e † [U
e T Z]k − BkF
kU0 V
≤ (1 + α)3 kA − [A]k kF + kS† N2 kF
eΣ
e † [U
e T SA]k − AkF ≤ (1 + α)3 kA − [A]k kF + 2kS† N2 kF
⇒ kU0 V
as required.
There are various choices of distribution DA from which S is sampled. The first choice is that S is
a subsampled randomized Hadamard transform. We consider another distribution from which S can be
sampled in Section B and show that if we use the alternative distribution discussed in Section B, then it
does not effect the bounds presented here. The following lemma bounds the additive error of the simplified
(non-private) algorithm when S is a subsampled Hadamard transform.
√
Lemma 34. Let N2 ∼ N (0, ρ2 )v×n . Then kS† N2 kF = O(ρ vn) with probability 99/100 over S ∼ DA .
Proof. Using Lemma 47, we have E[kN2 k2F ] = vnρ2 . The result follows by invoking Lemma 49 and
Markov’s inequality.

22

5.2

Complete Analysis

In this section, we prove the utility guarantee of Theorem 28. We first show the following result.
eΣ
e † [U
e T Z]k be the product of the factorization outputted by the algorithm
Theorem 35. Let Mk = UV
in Figure 3. Then with probability 1 − O(δ) over Φ ∼ DR and S ∼ DA ,
kMk − AkF ≤ (1 + α)kA − [A]k kF + 2kS† N2 kF + kN1 ([A]k Φ)† [A]k kF .
Proof. We prove the result by proving a series of results. We provide an upper and a lower bound on
minX,r(X)≤k kYX − BkF in terms of kA − [A]k kF and the output of the algorithm.
Lemma 36. Let A be the input matrix. Let Φ ∼ DR , S ∼ DA be as in Figure 3 . Let Y = ΦA + N1 and
B = A + S† N2 for N1 , N2 as defined in Figure 3. Then with probability 1 − δ over Φ ∼ DR ,
min kYX − BkF ≤ (1 + α)kA − [A]k kF + kN1 ([A]k Φ)† [A]k kF + kS† N2 kF .

X,r(X)≤k

T
Proof. Set r = k, P = [A]T
k , and Q = A in Lemma 7. Then using Lemma 7, we have
T
T
0
T
T
0
T
T
k[A]T
k X − A k ≤ (1 + α) min k[A]k − A kF , where X = argmin kΦ ([A]k X − A )kF .
X

X

Taking the transpose and the fact that the Frobenius norm is preserved under transpose and X0 = (([A]k Φ)T )† (AΦ)T ,
we have with probability 1 − δ over Φ ∼ DR ,
kAΦ([A]k Φ)† [A]k − AkF ≤ (1 + α)kA − [A]k kF .

(27)

Moreover, since ([A]k Φ)† [A]k has rank at most k and Y = AΦ+N1 , with probability 1−δ over Φ ∼ DR ,
min kYX − BkF ≤ kYΦ([A]k Φ)† [A]k − BkF

X,r(X)≤k

= kAΦ([A]k Φ)† [A]k + N1 ([A]k Φ)† [A]k − BkF
= kAΦ([A]k Φ)† [A]k + N1 ([A]k Φ)† [A]k − A − S† N2 kF
≤ kAΦ([A]k Φ)† [A]k − AkF + kN1 ([A]k Φ)† [A]k kF + kS† N2 kF

(28)

Combining equation (27) and equation (28), we have with probability 1 − δ over Φ ∼ DR ,
min kYX − BkF ≤ (1 + α)kA − [A]k kF + kN1 ([A]k Φ)† [A]k kF + kS† N2 kF .

X,r(X)≤k

(29)

Lemma 36 relates minX,r(X)≤k kYX − Bk with (1 + α)kA − [A]k kF , kN1 ([A]k Φ)† [A]k kF , and
Since U is the orthonormal basis for the column space of Y, we further have

kS† N2 kF .

min kUX − BkF ≤

X,r(X)≤k

min kYX − BkF .

X,r(X)≤k

(30)

Combining equation (29) and equation (30), we have with probability 1 − δ over Φ ∼ DR ,
min kUX − BkF ≤ (1 + α)kA − [A]k kF + kN1 ([A]k Φ)† [A]k kF + kS† N2 kF .

X,r(X)≤k

(31)

e = argminX,r(X)=k kS(UX − B)kF . Let
Lemma 37. Let U, B, A, S, N1 , and N2 be as above, and let X
DA be a distribution that satisfies (α, β)-subspace embedding. Then with probability 1 − 4δ over S ∼ DA ,
e − B)kF ≤ (1 + α)kA − [A]k kF + kS† N2 kF + kN1 ([A]k Φ)† [A]k kF .
k(UX

23

Proof. Set p = k/α, D = U and E = B in the statement of Lemma 8. Let us restrict our attention to rank
b = argminX,r(X)=k kUX − EkF and X
e = argminX,r(X)=k kS(UX − B)kF .
k matrices X and denote by X
Then we have with probability 1 − δ over S ∼ DA ,
b − BkF = (1 ± α)−1 kS(UX
b − B)kF
min kUX − BkF = kUX
X,r(X)=k

≥ (1 ± α)−1 min kS(UX − B)kF
X,r(X)

−1

= (1 ± α)

e − B)kF = (1 ± α)−2 k(UX
e − B)kF .
kS(UX

(32)

Combining equation (32) with equation (31), we have with probability 1 − 2δ over Φ ∼ DR and S ∼ DA ,
e − B)kF ≤ (1 + α)3 kA − [A]k kF + kS† N2 kF + kN1 ([A]k Φ)† [A]k kF .
k(UX
(33)
This completes the proof by scaling α by a constant factor.
e = argminX,r(X)≤k kS(UX−B)kF and lower
To finalize the proof of Theorem 35, we need to compute X
e and Z = SB, we get [U
e T Z]k = [U
e T SB]k =
e − B)kF . Invoking Lemma 33 with O = U
bound k(UX
e − SBkF . This implies that
argminX,r(X)≤k kUX
eΣ
e † [U
e T Z]k = argmin kS(UX − B)kF .
e=V
X

(34)

X,r(X)≤k

Using equation (34) in equation (33), and the fact that B = A + S† N2 , we have the final result.
e T Z]k − AkF − kS† N2 kF ≤ kUV
eΣ
e † [U
e T SA]k − BkF
eΣ
e † [U
kUV
≤ (1 + α)kA − [A]k kF + kS† N2 kF + kN1 ([A]k Φ)† [A]k kF .
eΣ
e † [U
e T Z]k − AkF ≤ (1 + α)kA − [A]k kF + 2kS† N2 kF + kN1 ([A]k Φ)† [A]k kF .
⇒ kUV
This completes the proof of Theorem 35.
p
Lemma 38. Let N1 ∼ N (0, ρ2 )m×t . Then kN1 ([A]k Φ)† [A]k kF = O(ρ km(1 + α)) with probability
99/100 over Φ ∼ DR .
Proof. Let C = N1 ([A]k Φ)† [A]k . Then CΦ = N1 ([A]k Φ)† [A]k Φ. Now ([A]k Φ)† [A]k Φ is a projection
unto a random subspace of dimension k. Since every entries of N1 is picked i.i.d. from N (0, ρ2 ), CΦ =
e 1 , where N
e 1 is an m × k matrix with every entries picked i.i.d. from N (0, ρ2 ).
N1 ([A]k Φ)† [A]k Φ = N
This is because we can write ([A]k Φ)† [A]k Φ is a projection unto a random subspace of dimension k.
Using Lemma 47, this implies that
h
i X
e 1 k2 =
e 1 )2 ] = kmρ2 .
E[kCΦk2F ] = E kN
E[(N
F
ij
i,j

The result follows using Markov’s inequality and the fact that kCΦk2F = (1 + α)kCk2F .
Theorem 28 now follows from Lemma 34, Lemma 38, Theorem 35, and the choice of ρ in Lemma 29.

6

Lower-bound for Low-rank Factorization When γ 6= 0

We give a reduction to the augmented indexing problem, AIND. It is defined as follows.
Definition 39. (AIND problem). Alice is given an N -bit string x and Bob is given an index ind ∈ [N ]
together with xind+1 , · · · , xN . The goal of Bob is to output xind .
24

The communication complexity for solving AIND is well known due to the result of Miltersen et al. [51].
Theorem 40. The minimum bits of communication required to solve AIND with probability 2/3, when the
message is sent only in one direction, i.e., either from Alice to Bob or from Bob to Alice, is Ω(n). This
lower bound holds even if the index, ind, and the string, x, is chosen uniformly at random.
The space lower bound in streaming model is shown by showing that a one-pass streaming algorithm
Alg yields a single round communication protocol for some function f . The idea is as follows. On input x,
Alice invokes Alg on its input to compute Alg(x). She then sends the state to Bob, who computes Alg(xky)
using his input y, and uses this to compute the function f . The communication is therefore the same as the
space required by the algorithm. In what follows, we use the notation C:i to denote the i-th column of the
matrix C.
Theorem 41. Let m, n, k ∈ N and α > 0. Then any randomized single-pass algorithm for (α, 5/6, O(m +
n), k)-LRA in the general turnstile model uses Ω((m + n)k/α) words.
Proof. We adapt the proof of Clarkson and Woodruff [11] for the case when γ 6= 0. Suppose m ≥ n and
let a = k/20α. Without loss of generality, a can be assumed to be at most n/2. Let ` be the word size.
We assume Alice has a string x ∈ {−1, +1}(m−a)a and Bob has an index ind ∈ [(m − a)a]. The idea is to
e constructed
define the matrix A with high Frobenius norm. The matrix A is the summation of the matrix A
by Alice and Ā constructed by Bob.
e as follows. We partition the set [a] in ` sets I1 , · · · , I` such that Ij :=
Alice constructs its matrix A
{(j − 1)a/` + 1, · · · ja/`} . Let MIi be an (m − a) × a/` matrix for all 1 ≤ i ≤ `. We form a bijection
between entries of x and the entries of M in the following manner. Every entry of MIi is defined by a
unique bit of x, i.e., (MIi )j,k = (−1)xd (10)i for d = (i − 1)(m − a)a + (k − 1)(m − a) + j.

 a×a
a×(n−a)

0
0
e =
A
, where M = MI1 · · · MI` .
(m−a)×(n−a)
M 0
Suppose Bob is given an index ind ∈ [(m − a)a] such that xind corresponds to the sub-matrix MIθ . Then
we can assume that Bob also knows every entry in the sub-matrix MIθ0 for θ0 > θ. Bob forms a second level
partition of the columns of MIθ in to k size groups G1 , · · · , Ga/k` of size a/`. Due to our construction,
there exists a unique r such that xind maps to an entry in the sub-matrix formed by columns indexed by
one of the second level partition Gr . Let Gr = {c, c + 1, · · · , c + k − 1} be the columns corresponding to
the k-size group of Iθ in which ind is present. As its input, Bob streams a matrix Ā which is an all-zero
matrix, except for entries Āc+i,c+i = ζ for 0 ≤ i ≤ k − 1. In other words, Bob inserts a scaled identity
matrix in the stream, where the scaling parameter ζ is large enough to make sure that most of the error of
any randomized algorithm is due to other columns of A. We set the value of ζ as a large polynomial in the
error of the algorithm.
e and send the state to
Alice runs its randomized single-pass algorithm for k-rank approximation on A
Bob. Bob completes the streaming algorithm using the state received by Alice and by streaming its own
e + Ā and it is
matrix Ā. Therefore, the one-pass randomized algorithm gets as input a matrix A = A
required to output a rank-k matrix B with additive error γ = O(m + n). We will show that any such an
output allows us to solve AIND. Denote by AGr the sub-matrix formed by the columns c, c+1, · · · , c+k−1.
Let us first understand the properties of the constructed matrix A. To compute the Frobenius norm
of this matrix, we need to consider two cases: the case for sub-matrices in which ind belongs, i.e, MIr ,
and the rest of the matrix. For the sub-matrix corresponding to the columns indexed by Gr , the columns
of AIθ have Euclidean length (ζ 2 + (m − a)100θ )1/2 . For θ0 < θ, every columns have Euclidean norm

25

0

(a(m − a))1/2 10θ . Therefore, we have the following:
kA −

[A]k k2F

0
((a − k)(m − a)100θ X a(m − a)100θ
+
≤
`
`
0

θ <θ

a)100θ

((a − k)(m −
a(m − a)100θ
+
≤ 2 · (100)θ m2 /` = Γ
`
99`
In order to solve (α, β, γ, k)-LRF, the algorithm needs to output B of rank at most k such that, with
probability 1 − β over its random coins,


h
i2
√
1
1
2
2
θ
+ 2γ 2
kA − BkF ≤ (1 + α) Γ + γ ≤ 2(1 + α)Γ + 2γ ≤ 2Γ + 100 k(m − a)
+
10 99


1
1
θ 2
θ
= 4 · (100) m /` + +100 k(m − a)
+ 2γ 2
+
10 99

1
1
Let us denote by Υ := 4 · (100)θ m2 /` + 100θ k(m − a) 10
+ 99
+ 2γ 2 . The proof idea is now the
following:
≤

(i) Columns of B corresponding to index set in Gr are linearly independent.
(ii) Bound the error incurred by kA − BkF in terms of the columns indexed by Gr .
The idea is to show that most of the error is due to the other columns in B; and therefore, sign in the
columns in A indexed by Gr agrees with that of the signs of those columns in B. This allows Bob to solve
the AIND problem as Bob can just output the sign of the corresponding position.
Let R := {ra/k + 1, · · · , (r + 1)a/k} and C := {c, · · · , c + k − 1}.
The following lemma proves that when ζ is large enough, then the columns of B corresponding to index
set Ir are linearly independent. This proves part (i) of our proof idea.
Lemma 42. Let B(C) := [B:c · · · B:c+k−1 ] be the columns corresponding to the sub-matrix formed by
columns c, · · · , c + k − 1 of B. If ζ ≥ 2Υ2 , then the columns of B(C) spans the column space of [A]k .
Proof. We will prove the lemma by considering the k × k sub-matrix, say Y, of B formed by the rows
indexed by R and the columns indexed by C. For the sake of brevity and abuse of notation, let us denote
the restriction of B to this sub-matrix Y := [Y:1 , · · · , Y:k ]. Suppose, for the sake of contradiction that the
vectors {Y:1 , · · · , Y:k } are linearly dependent. In other words, there exists a vector Y:i and real numbers
a1 , · · · , ak , not all of which are identically zero, such that
Y:i =

k
X

aj Y:j .

j=1,j6=i

From the construction, since Bob inserts a sub-matrix ζIk , we know that
k
X
(Yj,j − ζ)2 ≤ kA − Bk2F ≤ Υ.

(35)

j=1
k X
X

2
Yp,j
≤ kA − Bk2F ≤ Υ.

j=1 p6=j

26

(36)

From equation
(35) and choice of ζ, for all j, we have Yj,j ≥ Υ2 . Further, equation (36) implies that
√
Yp,j ≤ Υ. Let ĩ be the index in {1, · · · , k} \ {i} for which |aĩ | attains the maximum value. Then
Yi,i =

k
X

Υ2
aj Yi,j ≥ Υ2 implies that there is an ĩ ∈ {1, · · · , k} \ {i} such that |aĩ | ≥ √ .
k Υ
j=1,j6=i

Now consider the ĩ-entry of Y:i . Note that ĩ 6= i. Since Υ depends quadratically on m and γ, we have
k
X

√
√
√
Υ2
aj Yĩ,j ≥ |a|(Υ2 − k Υ) ≥ (Υ2 − k Υ) √ > Υ.
k Υ
j=1,j6=i
√
This is a contradiction because Yp,j ≤ Υ due to equation (36) for p 6= j. This completes the proof.
The following lemma proves part (ii) of our proof idea.
e :1 , · · · , V
e :k be the restriction of these vectors
Lemma 43. Let V:1 , · · · , V:k be the columns of B(C) and V
to the rows a + 1, · · · , n. Then column i of B can be written as linear combination of real numbers
2 ≤ 4/Υ3 .
ai,1 , · · · ai,k of the vectors V:1 , · · · , V:k such that, for all j and i ∈ R, ηi,j
P
Proof. Let M:1 , · · · M:a be the columns of M. The i-th row of B can be represented as ηi,j V:j , for real
numbers ηi,j , not all of which are identically zero. Then
Υ ≥ kA −

Bk2F

k
k X
k
X
X
X
2
2
e :i k2
≥
(ζ − Vr(a/k)+i,i ) +
Vr(a/k)+i,j +
kM:r(a/k)+i − V
i=1

i=1 j6=i

k
XX

+

i=1

2


ηi,j Vra/k+j,j +

X

ηi,j 0 Vra/k+j,j 0  +

j 0 6=j

i∈G
/ r j=1

X

2
As in the proof of Lemma 42, we have |Vr(a/k)+i,j
|≤

i∈G
/ r

√

M:i −

k
X

2

e :j
ηi,j V

.

j=1

Υ and |Vr(a/k)+i,i | ≥ Υ2 . Let ji be the index
√
such that |ηi,ji | is the maximum. Then the above expression is at least |ηi,ji |2 (Υ2 − k Υ)2 ≥ |ηi,ji |2 Υ4 /4.
Since this is less than Υ, the result follows.
e
We can now complete the proof.
√ First note that since M is a signed matrix, each Vi in the third term of
the above expression is at least Υ. Therefore, for all i ∈
/ S and all j
k
X

1/2
4k
e :j ≤ 4kΥ
=
.
ηi,j V
3/2
Υ
Υ
j=1

As M:i is a sign vector and if γ = O(m + n) = O(m), this implies that
X
i∈G
/ r

M:i −

k
X

2

≥

e :j
ηi,j V

j=1

X



4k
kM:i k 1 −
Υ
2

i∈G
/ r

≥ O((100)θ m2 /`) − O(100θ a)
k
X
i=1

e :i
M:r(a/k)+i − V

2

k m−a
X
X
e i )j )2
=
(Mj,r(a/k)+i − (V
i=1 j=1

≤ 100θ k(m − a)

27



1
1
+
10 99



+ O(100θ a)

Now, since there are in total
 k(m − a) entries in the submatrix formed by the columns indexed by Gr ,
1
1
at least 1 − 10 + 99 + o(1) fraction of the entries have the property that the sign of Mj,ra/k+i matches
e j,i . Since ind is in one of the columns of M:ra/k+1 , · · · M:ra/k+k , with probability at least
the sign of V

1
1
1 − 10 + 99 + o(1) , if Bob outputs the sign of the corresponding entry in B, then Bob succeeds in solving
AIND. This gives a lower bound of Ω((m − a)a) = Ω(mk`/α) space. The case when m ≤ n is analogous
and gives a lower bound of Ω(nk`/α). Thus, there is a lower bound of Ω((m + n)k`/α).
Acknowledgement. I would like to thank Adam Smith for many useful discussions. Even though he declined to co-author the paper, without his contributions, this paper would not have existed. I would also like
to thank Nithin Varma for proof reading the paper.

References
[1] Dimitris Achlioptas, Amos Fiat, Anna R Karlin, and Frank McSherry. Web search via hub synthesis.
In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 500–509.
IEEE, 2001.
[2] Dimitris Achlioptas and Frank McSherry. On spectral learning of mixtures of distributions. In Learning
Theory, pages 458–469. Springer, 2005.
[3] Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approximations. Journal of the ACM (JACM), 54(2):9, 2007.
[4] Yossi Azar, Amos Fiat, Anna Karlin, Frank McSherry, and Jared Saia. Spectral analysis of data.
In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 619–626.
ACM, 2001.
[5] Rajendra Bhatia. Matrix analysis, volume 169. Springer Science &amp; Business Media, 2013.
[6] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Lindenstrauss Transform
Itself Preserves Differential Privacy. In FOCS, pages 410–419, 2012.
[7] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Chen Li, editor, PODS, pages 128–138. ACM, 2005.
[8] Christos Boutsidis, D Woodruff, and P Zhong. Optimal principal component analysis in distributed
and streaming models. To appear in STOC 2016. Full version at arXiv:1504.06729, 2015.
[9] Joseph A Calandrino, Ann Kilzer, Arvind Narayanan, Edward W Felten, and Vitaly Shmatikov. ”
you might also like:” privacy risks of collaborative filtering. In Security and Privacy (SP), 2011 IEEE
Symposium on, pages 231–246. IEEE, 2011.
[10] Kamalika Chaudhuri, Anand D Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. In NIPS, pages 998–1006, 2012.
[11] Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In
STOC, pages 205–214, 2009.
[12] Kenneth L Clarkson and David P Woodruff. Low rank approximation and regression in input sparsity
time. arXiv preprint arXiv:1207.6365, 2012.
28

[13] Kenneth L Clarkson and David P Woodruff. Low rank approximation and regression in input sparsity
time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 81–90.
ACM, 2013.
[14] Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh
Annual ACM on Symposium on Theory of Computing, pages 163–172. ACM, 2015.
[15] Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang. Matrix approximation and
projective clustering via volume sampling. In Proceedings of the seventeenth annual ACM-SIAM
symposium on Discrete algorithm, pages 1117–1126. Society for Industrial and Applied Mathematics,
2006.
[16] Amit Deshpande and Santosh Vempala. Adaptive sampling and fast low-rank matrix approximation. In
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages
292–303. Springer, 2006.
[17] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the
twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages
202–210. ACM, 2003.
[18] J Dongarra and F Sullivan. Introduction the top 10 algorithms, special issue of. Computing in Science
and Engineering, 2(1), 2000.
[19] Petros Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, and V Vinay. Clustering large graphs via
the singular value decomposition. Machine learning, 56(1-3):9–33, 2004.
[20] Petros Drineas, Ravi Kannan, and Michael W Mahoney. Fast monte carlo algorithms for matrices ii:
Computing a low-rank approximation to a matrix. SIAM Journal on Computing, 36(1):158–183, 2006.
[21] Petros Drineas, Iordanis Kerenidis, and Prabhakar Raghavan. Competitive recommendation systems.
In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 82–90.
ACM, 2002.
[22] Petros Drineas and Michael W Mahoney. Approximating a gram matrix for improved kernel-based
learning. In Learning Theory, pages 323–337. Springer, 2005.
[23] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our Data,
Ourselves: Privacy Via Distributed Noise Generation. In EUROCRYPT, pages 486–503, 2006.
[24] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in
Private Data Analysis. In Shai Halevi and Tal Rabin, editors, TCC, volume 3876 of Lecture Notes in
Computer Science, pages 265–284. Springer, 2006.
[25] Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N Rothblum, and Sergey Yekhanin. Pan-Private
Streaming Algorithms. In ICS, pages 66–80, 2010.
[26] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and
Trends in Theoretical Computer Science, 9(3-4):211–407, 2014.

29

[27] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and Differential Privacy. In FOCS,
pages 51–60. IEEE Computer Society, 2010.
[28] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze Gauss: Optimal Bounds
for Privacy-Preserving Principal Component Analysis. In STOC, pages 11–20, 2014.
[29] Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank
approximations. Journal of the ACM (JACM), 51(6):1025–1041, 2004.
[30] Lars Grasedyck and Wolfgang Hackbusch. Construction and arithmetics of H-matrices. Computing,
70(4):295–334, 2003.
[31] Leslie Greengard and Vladimir Rokhlin. A new version of the fast multipole method for the laplace
equation in three dimensions. Acta numerica, 6:229–269, 1997.
[32] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217–288,
2011.
[33] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. In
Z. Ghahramani, M. Welling, C. Cortes, N.d. Lawrence, and K.q. Weinberger, editors, Advances in
Neural Information Processing Systems 27, pages 2861–2869. Curran Associates, Inc., 2014.
[34] Moritz Hardt and Aaron Roth. Beating randomized response on incoherent matrices. In STOC, pages
1255–1268, 2012.
[35] Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computation. In
STOC, pages 331–340, 2013.
[36] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of
dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing,
Dallas, Texas, USA, May 23-26, 1998, pages 604–613, 1998.
[37] Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially Private Online Learning. In Shie
Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT, volume 23 of JMLR Proceedings,
pages 24.1–24.34. JMLR.org, 2012.
[38] Wuxuan Jiang, Cong Xie, and Zhihua Zhang. Wishart mechanism for differentially private principal
components analysis. arXiv preprint arXiv:1511.05680, 2015.
[39] William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space.
Contemporary mathematics, 26(189-206):1, 1984.
[40] Daniel M. Kane and Jelani Nelson. Sparser Johnson-Lindenstrauss Transforms. J. ACM, 61(1):4,
2014.
[41] Ravindran Kannan, Hadi Salmasian, and Santosh Vempala. The spectral method for general mixture
models. In Learning Theory, pages 444–457. Springer, 2005.
[42] Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In SODA,
volume 5, page 1. SIAM, 2013.
30

[43] Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing
graphs with node differential privacy. In Theory of Cryptography, pages 457–476. Springer, 2013.
[44] Jon M Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM),
46(5):604–632, 1999.
[45] Avner Magen and Anastasios Zouzias. Low rank matrix-valued chernoff bounds and approximate
matrix multiplication. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete
Algorithms, pages 1422–1436. SIAM, 2011.
[46] Ivan Markovsky. Structured low-rank approximation and its applications. Automatica, 44(4):891–909,
2008.
[47] Ivan Markovsky. Low rank approximation: algorithms, implementation, applications. Springer Science &amp; Business Media, 2011.
[48] Frank McSherry. Spectral partitioning of random graphs. In Foundations of Computer Science, 2001.
Proceedings. 42nd IEEE Symposium on, pages 529–537. IEEE, 2001.
[49] Frank McSherry and Ilya Mironov. Differentially private recommender systems: building privacy into
the net. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery
and data mining, pages 627–636. ACM, 2009.
[50] Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input-sparsity time
and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium
on Theory of computing, pages 91–100. ACM, 2013.
[51] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson. On data structures and asymmetric communication complexity. In Proceedings of the twenty-seventh annual ACM symposium on
Theory of computing, pages 103–111. ACM, 1995.
[52] Arvind Narayanan and Vitaly Shmatikov. Robust de-anonymization of large sparse datasets. In Security and Privacy, 2008. SP 2008. IEEE Symposium on, pages 111–125. IEEE, 2008.
[53] John Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium
on, pages 117–126. IEEE, 2013.
[54] Nam H Nguyen, Thong T Do, and Trac D Tran. A fast and efficient algorithm for low-rank approximation of a matrix. In Proceedings of the forty-first annual ACM symposium on Theory of computing,
pages 215–224. ACM, 2009.
[55] Christos H Papadimitriou, Hisao Tamaki, Prabhakar Raghavan, and Santosh Vempala. Latent semantic
indexing: A probabilistic analysis. In Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART
symposium on Principles of database systems, pages 159–168. ACM, 1998.
[56] Christos H Papadimitriou, Hisao Tamaki, Prabhakar Raghavan, and Santosh Vempala. Latent semantic
indexing: A probabilistic analysis. In Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART
symposium on Principles of database systems, pages 159–168. ACM, 1998.

31

[57] Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through geometric
functional analysis. Journal of the ACM (JACM), 54(4):21, 2007.
[58] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In
Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on, pages 143–152.
IEEE, 2006.
[59] John Shawe-Taylor and Nello Cristianini. Kernel methods for pattern analysis. Cambridge university
press, 2004.
[60] Alwin Stegeman. Low-rank approximation of generic p\timesq\times2 arrays and diverging components in the candecomp/parafac model. SIAM Journal on Matrix Analysis and Applications, 30(3):988–
1007, 2008.
[61] Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning
in full-information and bandit settings. In Advances in Neural Information Processing Systems, pages
2733–2741, 2013.
[62] Jalaj Upadhyay. Random Projections, Graph Sparsification, and Differential Privacy. In ASIACRYPT
(1), pages 276–295, 2013.
[63] Jalaj Upadhyay. Differentially private linear algebra in the streaming model.
arXiv:1409.5414, 2014.

arXiv preprint

[64] Jalaj Upadhyay. Randomness efficient fast-johnson-lindenstrauss transform with applications in differential privacy and compressed sensing. arXiv preprint arXiv:1410.2470, 2014.
[65] Peter D Wentzell, Darren T Andrews, David C Hamilton, Klaas Faber, and Bruce R Kowalski. Maximum likelihood principal component analysis. Journal of Chemometrics, 11(4):339–366, 1997.
[66] David P. Woodruff. Personal communication. 2016.
[67] Zhengyou Zhang. Parameter estimation techniques: A tutorial with application to conic fitting. Image
and vision Computing, 15(1):59–76, 1997.

A

Auxiliary Results

We need the following result about product of pseudo-inverse in the proof of Lemma 49 and Claim 51.
Theorem 44. Let A and B be conforming matrices and either,
1. A has orthonormal columns (i.e., AT A is an identity matrix) or,
2. B has orthonormal rows (i.e., BBT is an identity matrix),
then (AB)† = B† A† .
We use the following variant of Pythagorean theorem in the proof of Lemma 14.
Theorem 45. (Pythagorean theorem). Let A and B be two matrices such that AT B is an zero matrix. Then
for any C = A + B, we have kCk2F = kAk2F + kBk2F .
We also need the following results for the privacy proof.
32

Theorem 46. (Lidskii Theorem [5]). Let A, B be n × n Hermittian matrices. Then for any choice of indices
1 ≤ i1 ≤ · · · ≤ ik ≤ n,
k
k
k
X
X
X
λij (A + B) ≤
λij (A) +
λij (B),
j=1

where

{λi (A)}ni=1

j=1

j=1

are the eigen-values of A in decreasing order.

√
Lemma 47. Let N ∼ N (0, ρ2 )m×n Gaussian matrix. Then with probability 99/100, kNkF = O(ρ mn).
Proof. The lemma follows from the following computation.


X
X
e 1 )2  =
e 1 )2 ] = kmρ2 .
E[kCΦk2F ] = E  (N
E[(N
ij
ij
i,j

i,j

The result follows using Markov’s inequality.
Lemma 48. (Sarlos [58]). Let σmax = σ1 ≥ · · · ≥ σm = σmin be the singular values of an m × n matrix A.
Let Φ ∈ Rn×m be sampled from a distribution that satisfies (α, β)-JLP. Let σ
emax = σ
e1 ≥ · · · ≥ σ
em = σ
emin
be the singular values of C := AΦ. Then σ
emax ≤ (1 + α)1/2 σmax and σ
emin ≥ (1 − α)1/2 σmin
Proof. Let y = Φx. From the definition, we have
σ
emax =

max

x∈Rm ,kxk2 =1

b
kAΦxk
2

b have the same rank and Φ ∼ DR , Lemma 7 and the choice of t gives, with
Let y = Φx. Since C and A
probability 1 − δ, (1 + α)kxk22 ≥ kyk22 ≥ (1 − α)kxk22 . This implies
σ
emax ≤ (1 + α)1/2

max

y∈Rm+n ,kyk2 =1

b 2 = (1 + α)1/2 σmax .
kAyk

b
The second part of the lemma follows similarly using the fact that σ
emin = minx∈Rm ,kxk2 =1 kAΦxk
2 and
2
kyk2 ≥ (1 − α).
Lemma 49. Let S be a v × m subsampled randomized Hadamard matrix, where v ≤ m and N ∈ Rv×n .
Then we have,
kS† N2 kF = kN2 kF .
Proof. One way to look at the action of S when it is a subsampled Hadamard transform is that it is a product
of matrices W and Π1..r , where Π1..r is the matrix formed by the first r rows of a random permutation
matrix and W is a randomized Walsh-Hadamard matrix formed by multiplying a Walsh-Hadamard matrix
with a diagonal matrix whose non-zero entries are picked i.i.d. from Rad(1/2).
Since WD has orthonormal rows, S† = (Π1..v WD)† = (WD)T (Π1..v )† .
kS† NkF = k(Π1..v WD)† NkF = k(WD)T Π†1..v NkF = kΠ†1..v NkF .
b 1..v Π
b T is an identity matrix, we have Π
b† =
Using the fact that Π1..v is a full row rank matrix and Π
1..v
1..v
b T (Π
b 1..v ΠT )−1 = Π
b T . The result follows.
Π
1..v
1..v
1..v
Theorem 50. Let DR be an (α, β)-subspace embedding for generalized regression (Definition 4). Then with
probability 1 − 2β over ΦT ∼ DR and Ψ ∼ DR , for any arbitrary m × n matrix A,
min kAΦXΨA − AkF ≤ (1 + α)2 kA − [A]k kF .

X,r(X)≤k

33

(37)

We give an alternate proof of Theorem 50. Our proof uses two optimization problems and uses the
solution to those optimization problem in a clever way. We feel that our proof is simpler. It also has explicit
solutions to the two optimization problems, which makes it easy to extend to the case of private low-rank
factorization and get a tight bound.
T
Proof. We will use Lemma 7 to prove the theorem. Set Φ = ΦT , P = [A]T
k , Q = A . Then for
e = argminX,r(X)≤k kΦT ([A]T X − AT )k, we have with probability 1 − β over ΦT ∼ DR ,
X
k
T
T
T
e
k[A]T
k X − A kF ≤ (1 + α) min k[A]k X − A kF
X,r(X)≤k

T
≤ (1 + α)k[A]T
k − A kF

e = (ΦT [A]T )† (AΦ)T . Since Frobenius norm is preserved under transpose, we have
Here X
k
kAΦ([A]k Φ)† [A]k − AkF ≤ (1 + α)kA − [A]k kF .

(38)

We now use Lemma 7 on the following regression problem:
min kTX − AkF ,

X,r(X)≤k

where T = AΦ([A]k Φ)† .

b = argminX,r(X)≤k kΨ(TX − A)kF . Since [A]k has rank k, Lemma 7 and equation (38) gives
Let X
with probability 1 − β over Ψ ∼ DR
b − AkF = kAΦ([A]k Φ)† X
b − AkF
kTX
≤ (1 + α) min k(AΦ)([A]k Φ)† X − AkF
X,r(X)≤k

≤ (1 + α)kAΦ([A]k Φ)† [A]k − AkF
≤ (1 + α)2 kA − [A]k kF .
b = (ΨT)† ΨA, with probability 1 − 2β over ΦT , Ψ ∼ DR , we have
Substituting the value of X
kAΦ([A]k Φ)† (ΨAΦ([A]k Φ)† )† ΨA − AkF ≤ (1 + α)2 kA − [A]k kF .

(39)

Since ([A]k Φ)† (ΨAΦ([A]k Φ)† )† has rank at most k, this completes the proof because
min kAΦXΨA − AkF ≤ kAΦ([A]k Φ)† (ΨAΦ([A]k Φ)† )† ΨA − AkF ≤ (1 + α)2 kA − [A]k kF .

X,r(X)≤k

B

Improving the Run-time Efficiency of Factorization

If we want a more efficient algorithm, then we can replace S by the product of a v × v 0 subsampled randomized Hadamard matrix and a v 0 × m sparse subspace embedding matrix, also known as count-sketch
matrix [13, 50] (here, v = O(kα−3 log(k/α)) and v 0 = O(k 2 α−4 log6 (k/α))). Both of these matrices
satisfies Definition 5 [12, Lemma 46]. In that case, we have the following claim, which is analogous to the
result presented in Lemma 49. In other words, we can use the following claim everywhere where Lemma 49
is used.
Claim 51. Let S be the product formed by a v × v 0 subsampled randomized Hadamard matrix and a v 0 × m
sparse subspace embedding matrix. Then with high probability, for any v 0 × n matrix N, we have
kS† NkF = kNkF .
34

Proof. First note that S = (Π1..v0 WD1 )(HD2 ) , where D1 is a v ×v diagonal matrix with non-zero entries
sampled from Rad(1/2), D2 is an m × m diagonal matrix with non-zero entries sampled from Rad(1/2),
W is a normalized Hadamard matrix, and H is a matrix formed using a random hash function h : [m] → [v]
such that entry Hijp= 1 if and only if h(j) = i and 0, otherwise. Therefore, S† = ((Π1..v0 WD1 )(HD2 ))† .
We claim that (v/m)HD2 is a matrix with orthonormal
p rows. First note that D2 is a diagonal matrix
with only ±1 non-zero entries; therefore, if we prove that v/mH is a matrix with orthonormal rows, then
we are done. Now, consider an entry (HHT )ij . Let Hi: denote the i-th row of the matrix H. Note that H is
a full row-rank matrix. Therefore, by the construction of the matrix H, we have the following:
(
0
i 6= j
(HHT )ij =
,
kHi: k0 i = j
where kHi: k0 denotes the number of non-zero entries in the row Hi: . Now, since h(·) is a random function
that maps to every entry in [v] uniformly, E[kHi: k0 ] = m/v. Chernoff bound now gives that, with high
probability, kHk0 = m/v. Therefore, v/m(HHT )ij = 1 when i = j. In other words, with high probability,
(HHT )−1 = (v/m)I.
p
Now returning to the proof, conditioned on the event that v/mHD2 has orthonormal rows, we can
e = (Π1..v0 WD1 ). Then we can invoke the proof of Lemma 49
write S† = (HD2 )† (Π1..v0 WD1 )† . Let S
e
b
to say that SN gives a matrix N with entries of N permuted according to the permutation Π1..v0 . Therefore,
b F for some random v × n Gaussian matrix N
b whose entries are sampled
b 2 )† Nk
we have kS† NkF = k(HD
i.i.d. from N (0, 1).
b Therefore, with high
b = D† H† N.
Since D2 is matrix with orthonormal columns, we have (HD2 )† N
2
probability,
b F = kHT (HHT )−1 Nk
b F = v kHT Nk
b F.
kS† NkF = kH† Nk
m
v
b 2 as
Now, we can write m
kHT Nk
F
!2
m X
m n
n
v
X
X
v
v
v XX b2
b 2 =
b k,j
b 2
kHT Nk
H
N
=
Nh(i),j = kNk
k,i
F
F
m
m
m
i=1 j=1

C

i=1 j=1

k=1

Problems Studied in Previous Works

Table 3 gives all the previous results under the assumptions made and the problem studied. Below, we define
each of these problems and their difference from the problem studied in this paper.
Hardt and Roth [34] and Upadhyay [63] studied the following problem.
Problem 2. (Approximation with respect to the Frobenius norm). Given parameters α, β, τ , a private
e k such that
m × n matrix A (where m  n) and the target rank k, find a rank-k matrix A
h
i
e k kF ≤ (1 + α)kA − [A]k kF + τ ≥ 1 − β.
Pr kA − A
Here, two matrices are neighbouring if they differ by single row of unit norm.

35

Theorem 28
Problem 1

(ε, δ)-differential privacy
Theorem 15
(ε, δ)-differential privacy
Hardt and Roth [34]

Problem 2

(ε, δ)-differential privacy
Hardt and Roth [34]
(ε, δ)-differential privacy
Upadhyay [63]

Problem 3

α,

τ =O

A − A0 = es vT
A − A0 = es vT
α = O(1), τ = O
A − A0 = es vT

Kapralov and Talwar [42]

kAk2 − kA0 k2 = 1

Dwork et al. [28]
(ε, δ)-differential privacy
Jiang et al. [38]
ε-differential privacy

√

α = O(1), τ = O

α = O(1),

ε-differential privacy
Hardt and Price [33]

Assumptions
No assumptions


q
√
 √log(1/δ)
1
k
+
km + n(1+α)
α3
α
ε

A − A0 = uvT 
No assumptions

√
(1+α)k(m+n) log(1/δ)
α,
τ =O
αε

(ε, δ)-differential privacy

(ε, δ)-differential privacy
Problem 4

Neighbouring Data
kA − A0 kF = 1 

√

km log(k/δ)
ε

No coherence assumption


km log(k/δ)
ε

τ =O

Incoherent matrix

q
pn
+ k µ0 kAkF log(k/δ)
ε
m



k2

√

√

n
+ k log(1/δ)
ε
No assumptions


n+m log(k/δ)
ε

Singular-value
 3  separation
α = 0,
τ = cλ1 , where λ1 = Ω nk
εc6
A − A0 = es eT
Singular-value
separation
and incoherent
matrix
t
 2p

k
α = 0,
τ = O ε (µ + k log n) log(1/δ)

A − A0 = es vT

No assumptions



α = 0,
τ =O
A − A0 = es eT
t

α = 0,

τ =O


√
k n log(1/δ)
ε

No assumptions
n log n
ε



Table 3: Comparison of Models for Differentially-private k-Rank Approximation (β = O(1), u and v are unit vectors,
es is the s-th standard basis, and µ0 and µ are coherence of the private matrix).

Difference from this paper. We consider low-rank factorization while Problem 2 studied only lowrank approximation. Moreover, the granularity of privacy we consider is more general than theirs.
We can also study low-rank approximation when the approximation metric is spectral norm, which was the
focus of Kapralov and Talwar [42], Hardt and Roth [35], and Hardt and Price [33].
Problem 3. (Approximation with respect to the spectral norm). Given parameters α, β, τ , a private
e k such that
m × n matrix A (where m  n) and the target rank k, find a rank-k matrix A
h
i
e k k ≤ (1 + α)kA − [A]k k + τ ≥ 1 − β.
Pr kA − A
Hardt and Price [33] and Jiang et al. [38] consider two matrices as neighboring if they differ in
exactly one entry by at most 1. Kapralov and Talwar [42] considered two matrices as neighboring if
the difference of their spectral norm is at most 1.
Difference from this paper. We consider low-rank factorization with respect to the Frobenius norm
while Problem 3 studied only low-rank approximation with respect to the spectral norm. Moreover,
granularity of privacy we consider is more general than theirs.
Approximating the right singular vectors. Dwork et al. [28] studied the following problem.
Problem 4. Given parameters α, β, τ and an m × n private matrix A (where m  n)), compute a

36

e k such that
rank-k matrix B

ek
Pr AT A − B

≤

min
rank(Bk )≤k


+ τ ≥ 1 − β,

AT A − Bk

where |||·||| denotes either the spectral or the Frobenius norm.
Dwork et al. [28] consider two matrices neighbouring if they differ by at most one row. They further
assume that the rows are normalized; therefore, their definition of neighbouring matrices is the same
as Hardt and Roth [34].
Difference from this paper. We consider low-rank factorization of both the right and the left singular
vectors while Problem 4 studied low-rank “approximation” of the right singular vectors. Moreover,
granularity of privacy we consider is more general than theirs.
Lemma 52. Let B and C be two conforming matrices. Let σmin (B) be the least non-zero singular value of
B and σmax (B) be the largest singular value of B. Then
σmin (C)kBkF ≤ kCBkF ≤ σmax (C)kBkF .
Proof. Let B = [B1 , . . . , Bn ] be the column partitioning of B, then the definition of the Frobenius norm,
we have
n
X
kCBk2F =
kCBi k22
i=1

Using the fact that
n
o
σmin (C) = min xT CT Cx : kxk2 = 1 ≤ kCBi k2 /kBi ki
x
n
o
σmax (C) = max xT CT Cx : kxk2 = 1 ≥ kCBi k2 /kBi ki ,
x

for all i, we have Therefore, we have
n
n
n
X
X
X
σmin (C)2
kBi k2i ≤
kCBi k22 ≤ σmax (C)2
kBi k2i
i=1

i=1

i=1

or, σmin (C)kBkF ≤kCBkF ≤ σmax (C)kBkF .

37

