On Low-Space Differentially Private Low-rank Factorization in the
Spectral Norm

arXiv:1611.08954v1 [cs.DS] 28 Nov 2016

Jalaj Upadhyay
College of Information Science and Technology
Pennsylvania State University
jalaj@psu.edu

Abstract
Low-rank factorization is used in many areas of computer science where one performs spectral analysis on large sensitive data stored in the form of matrices. In this paper, we study
differentially private low-rank factorization of a matrix with respect to the spectral norm in
the turnstile update model. In this problem, given an input matrix A ∈ Rm×n updated in
the turnstile manner and a target rank k, the goal is to find two rank-k orthogonal matrices
Uk ∈ Rm×k and Vk ∈ Rn×k , and one positive semidefinite diagonal matrix Σk ∈ Rk×k such
that A ≈ Uk Σk VkT with respect to the spectral norm.
Our main contributions are two computationally efficient and sub-linear space algorithms for
computing a differentially private low-rank factorization. We consider two levels of privacy. In
the first level of privacy, we consider two matrices neighboring if their difference has a Frobenius
norm at most 1. In the second level of privacy, we consider two matrices as neighboring if their
difference can be represented as an outer product of two unit vectors. Both these privacy levels
are stronger than those studied in the earlier papers such as Dwork et al. (STOC 2014), Hardt
and Roth (STOC 2013), and Hardt and Price (NIPS 2014).
As a corollary to our results, we get non-private algorithms that compute low-rank factorization in the turnstile update model with respect to the spectral norm. We note that, prior to
this work, no algorithm that outputs low-rank factorization with respect to the spectral norm
in the turnstile update model was known; i.e., our algorithm gives the first non-private low-rank
factorization with respect to the spectral norm in the turnstile update mode.
Our algorithms generate private linear sketches of the input matrix. Therefore, using the
binary tree mechanism of Chan et al. (TISSEC: 14(3)) and Dwork et al. (STOC 2010), we get
algorithms for continual release of low-rank factorization under both these privacy levels. This
gives the first instance of differentially private algorithms with continual release that guarantees
a stronger level of privacy than event-level privacy.

Keywords. Differential privacy, low-rank factorization, continual release, turnstile update model.

1

Introduction

Spectral analysis of matrices is used in many areas where large sensitive data are stored in the
form of matrices. A partial list includes data mining [4], recommendation systems [17], information
retrieval [43, 48], web search [1, 37], clustering [12, 15, 39], and learning distributions [2, 34]. A
general technique used in the literature involving such analysis first computes an approximate
1

low-rank factorization (LRF) of the matrix to avoid the curse of dimensionality with the hope
that the output from using the LRF does not “differ by much” from the output from using the
original data matrix. These algorithms often do not consider privacy (or use ad-hoc anonymization
methods) and do not account for dynamic data matrices. On the other hand, the limitations of
ad-hoc anonymization of these data has been exemplified by the denonymization of the Netflix
datasets [41] and the real-world data changes dynamically. This raises two natural questions:
(i) Can we efficiently perform LRF under the spectral norm while preserving the privacy
of the dynamic data matrix?
(ii) Can we release LRF under the continual release model [21]?
We answer these questions in the affirmative. Specifically, we give two differentially private
algorithms that receive an m × n matrix in the turnstile update model and output a k-rank factorization with respect to the spectral norm. Our algorithms efficiently compute a small space
linear sketches of the private matrix. We use the private matrix only when generating the linear
sketches; therefore, our algorithms can be easily modified to get differentially private algorithms
under continual release (i.e., the output is released at every time epoch) by using the binary tree
mechanism [8, 21].
In the recent past, there has been a lot of attention to a related problem of differentially private
low-rank approximation (LRA) with respect to the spectral norm [24, 27, 29, 35] leading to an
optimal approximation error. However, these algorithms run in O(mnk) time, use O(mn) space,
and assume that the matrix is static. It is easy to see that, if there are no time or space constraints,
then LRA can be used to give LRF in polynomial time. However, it is not known how to efficiently
factorize a matrix in sub-linear space. Even in the non-private setting, there is no known algorithm
that computes spectral approximation in the turnstile update model — the only algorithm that
computes an LRA is under Frobenius norm by Boutisidis et al. [7] and Clarkson and Woodruff [11].
Unfortunately, the algorithm of Boutsidis et al. [7] is not robust against noise. In a closely related
work, Upadhyay [54] gave a differentially private algorithm for LRF in the turnstile update model
when the approximation metric is the Frobenius norm. This algorithm can be seen as a robust
version of the algorithm of Boutsidis et al. [7].
One natural point to start would be to see if one could use the existing algorithm that gives
approximation under Frobenius norm.Unfortunately, Karnin and Liberty [36] observed that even
though the exact solution of LRF is the same with respect to both the Frobenius and the spectral
norm, the same cannot be said about their approximate solutions. Moreover, even though the
spectral norm and Frobenius norm are trivially within the factor of each other, the same cannot be
said about their approximate solutions. Therefore, it is not clear if we can use the algorithms of
Upadhyay [54] and Boutsidis et al. [7] to give algorithms for LRF with respect to the spectral norm.
On the other hand, there is an instance of algorithm by Halko et al. [26] that gives approximation
under both the spectral as well as the Frobenius norm. However, their algorithm is not in a turnstile
update model.

1.1

Formal Problem Description

In this paper, we study differentially private LRF in the turnstile update model when the approximation metric is the spectral norm. In the turnstile update model, an update is in the form
of triples {i, j, sτ }, where 1 ≤ i ≤ m, 1 ≤ j ≤ n, sτ ∈ R for all τ ≥ 1. This leads to a change in
2

the (i, j)-th entry of the private matrix A as follows: Ai,j ← Ai,j + sτ . We first give the formal
definition of differential privacy.
Definition 1. A randomized algorithm M gives (ε, δ)-differential privacy, if for all neighbouring
databases (presented in the form of matrices) A and A′ , and all subsets S in the range of M,
Pr[M(A) ∈ S] ≤ eε Pr[M(A′ ) ∈ S] + δ over the coin tosses of M.
We can now formally define the main problem we address in this paper.
Problem 1. ((ε, δ, β, γ, ζ, k)-LRF). Given parameters ε, δ, γ, β, ζ, the target rank k, and a private
m × n matrix A updated in the general turnstile update model, output (under continual release) an
e k, Σ
e k, V
e k such that
(ε, δ)-differentially private rank-k factorization U
h
i
e kΣ
e kV
e T k2 ≤ γkA − [A]k k2 + ζ ≥ 1 − β,
Pr kA − U
k

where k · k2 denotes the spectral norm and [A]k is the best rank-k approximation of A. We refer
the term γ as the multiplicative error and the term ζ as the additive error. We call the tuples (ε, δ)
the privacy parameters.
Our problem statement is more general than principal component analysis in the sense that we
require approximation to both the left and the singular vectors. We discuss this in more details
in Appendix B.
Granularity of Privacy: In the past, differentially private LRA with respect to the spectral
norm have been proposed with varying levels of privacy. Kapralov and Talwar [35] considered
two matrices neighboring if the difference of their spectral norm is at most 1. Dwork et al. [24]
considered two row-normalized matrices neighboring if they differ in one row. Hardt and Price [27]
and Hardt and Roth [29] considered two matrices as neighboring if they differ exactly in one entry.
In this paper, we consider even stronger levels of privacy. This matrices deals with streaming
matrices; therefore, for the sake of discussion and ease of comparison of privacy model, below we
define the granularity of privacy with respect to neighboring matrices. Two streams are said to be
neighboring if they are formed using neighboring matrices.
In the first privacy level, Priv1 , we call two matrices A and A′ as neighboring if kA − A′ kF ≤ 1,
where k·kF denotes the Frobenius norm. In the second privacy level, Priv2 , we consider two matrices
are neighboring if kA − A′ kF ≤ 1 and A − A′ is a rank-1 matrix. In other words, the matrices differ
in only one spectrum by at most 1. Both these privacy notions are motivated by natural scenarios
that are not captured by the privacy level studied in previous works [24, 27, 29]. For example, Priv2
is a natural choice where the spectrum of the input matrix is the key feature, which is the case in
scenarios where spectral analyses are performed. The choice of Priv1 is motivated by the examples
listed in Upadhyay [54], where the presence or absence of an individual in a social graph can lead
to a change of at most 1 in the Frobenius norm of the corresponding adjacency matrix. We refer
the readers to Upadhyay [54] for more details. Another notable example where Priv2 make sense is
the word2vec model.

1.2

Contributions of This Paper

All the earlier works [27, 29, 35] use an approach known as the subspace iteration. A subspace
iteration algorithm runs for k rounds. In every iteration, the algorithm computes (and stores) the
3

top singular vector of the matrix, say v, and updates the matrix A as follows: A ← A−(vT Av)vvT .
Our key insight is that we can compute the top-k singular vector in one step (even in the turnstile
update model) by using linear sketches. This also allows us to reduce the additive
√ error as we do
not have to add noise k times to preserve the privacy in every iteration, giving us k improvement
over private algorithms that use subspace iteration.
e hides a log n factor and denote
Throughout this section, we assume δ = o(1/n2 ) and let O(·)
by ∆k (A) := kA − [A]k k2 . We state our results assuming m ≥ n. All our results hold true for
m < n with the roles of m and n reversed. Our algorithms are also efficient because all the costly
computations are done on low-dimensional sketches and the sketches themselves can be generated
and updated efficiently using known techniques [11, 33].
LRF With Respect to Spectral Norm Under Priv1 : Our first algorithm, Spectral-LRF,
is based on the following intuition. Let [U]k [Σ]k [V]T
k be a singular-value decomposition of [A]k .
e :=
Therefore, if an orthonormal column matrix U is a “faithful” representation of [U]k , then X
T
e
[Σ]k [V]k ≈ argminr(X)≤k kUX − Ak and kUX − Ak2 ≈ k[A]k − Ak2 . We show that the matrix U
can be computed from a linear sketch. If we pick S to be a random projection matrix such that,
e −
simultaneously for all X, kS(UX − A)k2 ≈ k(UX − A)k2 with high probability, then kS(UX
A)k2 ≈ k[A]k − Ak2 with high probability. In other words, we need to store SA and the linear
sketch used to compute U, and output the product of U and argminr(X)≤k kS(UX − A)k2 . We
show the following.
Theorem 2. (Informal statement of Theorem 11). Let m, n ∈ N (where m ≥ n), (ε, δ) be the
privacy parameters, and
 k be the desired rank of the factorization. Let α ∈ (0, 1) be an arbitrary
constant and η = max k2 , α−1 . Given an m × n matrix A in the turnstile update model, there
exists an efficient (ε, δ)-differentially private algorithm that uses Oδ (mηα−1 + nηα−3 ) space and
outputs a k-rank factorization Uk , Σk , Vk such that, with probability at least 9/10 over the coin
tosses of the algorithm,

 √
√
−2
m
+
n
+
α
(1 + α)
T
e
.
∆k (A) + O
kA − Uk Σk Vk k2 ≤
(1 − α)2
(1 − α)3/2 ε

In practice, k ≪ max {m, n} and α is a small constant. In that case, we have (1−α)−1 ≈ (1+α).
If we scale the value of α appropriately, then we have the following corollary to Theorem 2.

Corollary 3. (Informal statement of Corollary 17). Let m, n, ε, δ be as in Theorem 2 with m ≥
n. Then there exists an efficient (ε, δ)-differentially private algorithm under Priv1 that solves 
e (√m + √n)ε−1 .
(ε, δ, γ, 1/10, ζ, k)-LRF in Oδ (mηα−1 +nηα−3 ) space, where γ := (1 + α) and ζ := O
Remark 1. Hardt and Roth [29, Thm 1.2] showed that any differentially private algorithm incurs
√
an additive error ζ = Ω(ε−1 n) for an n × n matrix. Their lower bound holds even when the
algorithm can access the input matrix any number of times. Corollary 3 shows that we can achieve
the same bound, up to a logarithmic factor, even when the matrix is updated in the turnstile manner
at the cost of small multiplicative error that depends only on the (k + 1)-th singular value.

Improving the Space Bound Under Priv2 : The algorithm Spectral-LRF had a space requirement that depends on the dimension of both S and U. However, if the matrix is almost square, then
the storage required to store SA is much higher than that to store the sketch that is used to compute
4

U. A direct observation then is that, if we can simultaneously generate an orthonormal matrix V
e := [Σ]k ≈ argminr(X)≤k kUXVT −Ak2 . Further,
which is a “faithful” representation of [V]k , then X
e T − A)Rk2 ≈
if we pick Q and R that satisfy similar properties as S in Section 1.2, then kQ(UXV
e T −A)Rk2 ,
k[A]k −Ak2 Therefore, we can output the product of matrices U, argminr(X)≤k kQ(UXV
and VT . This forms the basis of Low-Space-LRF.
Theorem 4. (Informal statement of Theorem 19). Let m, n ∈ N (where m ≤ n) and ε, δ be the
input parameters. Letk be the desired rank of the factorization. Let 0 < α < 1 be an arbitrary
constant and η = max k2 , α−1 . Given an m × n matrix A in the turnstile update model, there exists an efficient (ε, δ) differentially private algorithm that outputs a k-rank factorization Uk , Σk , Vk
using Oδ ((m + n)ηα−1 log(1/δ)) space, such that with probability at least 9/10 over the coin tosses
of the algorithm,
 −1
√
√ 
m
+
n
kα
ln(1/δ)
+
(1 + α)2
T
e
∆k (A) + O
.
kA − Uk Σk Vk k2 ≤
4
3
(1 − α)
ε(1 − α)
As before we get analogous results to Corollary 3.

Corollary 5. (Corollary 29, informal). Let m, n, ε, δ be as in Theorem 2 and α ∈ (0, 1) be a
small constant. Then there exists an efficient (ε, δ) differentially private algorithm that solves

e (√m + √n)ε−1 .
(ε, δ, γ, 1/10, ζ, k)-LRF using O((m+n)ηα−1 log(1/δ)) space, where γ := (1 + α) and ζ := O

Remark 2. The dependency of space complexity on α is unavoidable. To see this, consider a matrix
A of rank k + 1. In this case, approximation with respect to the Frobenius norm and spectral norm
are equivalent. However, due to the result of Upadhyay [54], any algorithm that achieves (1 + α)
multiplicative error and O(n) additive error has to use Ω(nk/α) space. Therefore, one cannot hope
to get an LRA under spectral norm with no multiplicative error and low space under the turnstile
update model.

1.3

Applications of Our Results

Application in Continual Release: One of the characteristics of our algorithms is that U is
computed from a linear sketch of the private input matrix and SA is a linear sketch. This implies
that we can use the binary tree mechanism [8, 21] to get a low-rank factorization under continual
release by paying an O(log T ) factor in the additive error, where T is the number of updates. This
is stated in the form of the following results (for a small constant α ∈ (0, 1)).
Theorem 6. (Informal statement of Theorem 30). Let m, n, ε, δ be as in Theorem 2. Then there exists an efficient (ε, δ)-differentially private algorithm under Priv1 that solves (ε, δ, γ, 1/10, ζ, k)-LRF

e (√m + √n)ε−1 log T .
under continual release for T time epochs, where γ := (1 + α) and ζ := O

Theorem 7. (Informal statement of Theorem 31). Let m, n, ε, δ be as in Theorem 4. Then there exists an efficient (ε, δ)-differentially private algorithm under Priv2 that solves (ε, δ, γ, 1/10, ζ, k)-LRF

e (√m + √n)ε−1 log T .
under continual release for T time epochs, where γ := (1 + α) and ζ := O

Application in Non-private Setting: As an immediate result of Theorem 2, when ε → ∞, we
get a non-private algorithm that achieves low-rank factorization in the turnstile update model with
respect to the spectral norm. Prior to this work, no algorithm that outputs LRA with respect to
the spectral norm in the turnstile update model was known.
5

Theorem 8. Let m, n be as in Theorem 2 and α ∈ (0, 1). Given a matrix A ∈ Rm×n in the
turnstile update model, there exists an efficient algorithm that uses O(mkα−1 + nα−4 ) space and
outputs a k-rank factorization Uk , Σk , Vk such that kA − Uk Σk VkT k2 ≤ (1 + α)∆k (A).
Similarly, we can improve the space bound of the algorithm by setting ε → ∞ in Theorem 2.
Theorem 9. Let m, n be as in Theorem 2 and α ∈ (0, 1). Given a matrix A ∈ Rm×n in the
turnstile update model, there exists an efficient algorithm that uses O((m + n)kα−1 ) space and
outputs a k-rank factorization Uk , Σk , Vk , such that kA − Uk Σk VkT k2 ≤ (1 + α)∆k (A).

1.4

Technical Overview

In this section, we only present the proof idea for the correctness of Spectral-LRF. The proof idea
for the correctness of Low-Space-LRF and the algorithms for continual releases follows from the
intuition given in Section 1.2. The basic idea behind Spectral-LRF is to compute matrix U and
find S with certain properties. Proving that our candidate choices for S and U satisfy the desired
properties turns out to be the main technical challenge of this paper. The main complication here
is that the spectral norm does not satisfy the Pythagorean theorem, which forms a key ingredient
in the proof when the approximation guarantees are in the Frobenius norm [54]. In what follows,
we use the private matrix A to give the intuition. In the actual proof, there is an extra Gaussian
matrix due to use of the Gaussian mechanism to preserve privacy. We show that if we use the
Gaussian mechanism appropriately, the additive error scales optimally with the dimensions of the
private matrix A.
r(·) denote the rank of the
Let [U]k [Σ]k [V]T
k be a singular-value decomposition of [A]k and
√
matrix. Let Φ be a matrix that satisfies Lemma 10 for parameters ( α/k, 1/10). Then our choice
of U is an orthonormal basis of the column space of AΦ. This implies that minr(X)≤k kUX−Ak2 ≤
minr(X)≤k kAΦX−Ak2 . We use two optimization problems to prove that U is a good approximation
to [U]k : minX kΦT ([V]k X − AT )k2 (Problem 1) and minX k([V]k X − AT )k2 (Problem 2). The
result follows by combining equation (1), equation (2), and equation (3) listed below.
Since Problem 1 is a minimization problem over all allowable matrices X, using Theorem 44
e = (ΦT [V]k )† ΦT AT . Since the rank of
and the singular value decomposition of ΦT [V]k , we get X
T
†
([V]k (Φ [V]k ) ) is at most k,
min kUX − Ak2 ≤ min kAΦX − Ak2

r(X)≤k

r(X)≤k

≤ kAΦ([V]k (ΦT [V]k )† )T − Ak2
e − AT k2 .
= k[V]k X

(1)

e is a solution to Problem 1 and X
b is a solution to Problem 2, then
We then show that, if X
e − AT k2 ≤ (1 − α)−1 k([V]k X
b − AT )k2 .
k[V]k X

(2)

Now if we pick X = [Σ]k [U]T
k in Problem 2, then

b − AT k2 = min k([V]k X − AT )k2
k[V]k X
X

≤ kAT − [V]k [Σ]k [U]T
k k2 = ∆k (A).
6

(3)

We sample S from a distribution of random projection matrices that satisfies the JohnsonLindenstrauss lemma. To prove that our choice of S satisfies the required property, we introduce
the optimization problem: minX kUX − Ak2 . Since X can have rank at most the rank of A,
b = UT [UUT A] = argminX kUX − Ak2 . This implies that
using Theorem 44, we have that X
b − A) = UT (UUT − I)A = 0. We use this fact, the sub-additivity and sub-multiplicativity
UT (UX
of the spectral norm, and the fact that kSk2 ≈ 1 if S satisfies the Johnson-Lindenstrauss lemma to
prove that S satisfies the required property.
To preserve the privacy of Spectral-LRF, we note that the private matrix is used twice: when
we compute the matrix U and when we compute SA. Therefore, if we add appropriately scaled
Gaussian matrices at these stages, then the privacy of the algorithm follows from the fact that
differential privacy is preserved under post-processing. For the privacy proof of Low-Space-LRF,
we use the idea used by Upadhyay [54] to use both the input and the output perturbation.

1.5

Comparison with Previous Works

All the previous private algorithms compute low-rank 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 store the output (Dwork et al. [24] requires O(n2 ), but they work with
covariance matrices). Unlike this work, previous works also assume structured private matrix, like
matrices with singular value separation [29, 27, 35]. Previous works have studied three variants
of LRA. Dwork et al. [24] only approximate the right-singular vector while Hardt and Roth [29]
(and subsequently, Hardt and Price [27] who improved the result of Hardt and Roth [29] and
Upadhyay [52]) approximates both right and left singular vectors. Kapralov and Talwar [35] and
Jiang et al. [31] considered (ε, 0)-differential privacy. On the other hand, our algorithm outputs a
factorization with (ε, δ)-differential privacy. In this sense, our problem is closely related to Hardt
and Price [27]. We give the technical descriptions and the differences between Problem 1 and all
the previously studied problems in Appendix B. Here, we only compare this work with the results
of Hardt and Price [27] and Upadhyay [52]. We give a comparison of the results in Table 1. Below,
we enumerate the key differences between our result and that of Hardt and Price [27].
1. Space efficiency. The algorithms of Hardt and Price [27] and Upadhyay [52] use O(mn) space.
On the other hand, both of our algorithms use sub-linear space.
2. Approximation p
error. Both of our bounds improve the additive error of Upadhyay [52] by a
factor of k3/2 α2 log(1/δ). To make a reasonable comparison with Hardt and Price [27], we
consider their
p result without coherence assumption. Hardt and Price [27] incurs an additive
e 1 k(m + n)ε−1 ), where σ1 is the maximum singular value of the input matrix.
error O(σ
We√can rewrite our results to say that we incur an additive error that depends on ασk+1 +
e m + n/ε). In most real world scenarios, σk+1 ≪ σ1 . In other words, we improve the
O(
result of Hardt and Price [27] if σ1 is large. Recall that the dependency on α is unavoidable
for low-space algorithm (see, Remark 2).
3. Streaming constraints. Hardt and Price [27] is a private version of the iterative algorithm
of Halko et al. [26]. The algorithm of Upadhyay [52] is one-pass, but assumes that the
matrix is streamed row-wise. A row-wise update is an easier problem (with respect to the

7

Theorem 11
(ε, δ)-differential privacy
Theorem 19
(ε, δ)-differential privacy
Kapralov and Talwar [35]

Neighbouring Data
Assumptions
kA − A′ kF = 1
No assumption
A − A′ = uvT
No assumption
kAk2 − kA′ k2 = 1

(ε, 0)-differential privacy

Singular-value separation (SVS)

Upadhyay [52]

A − A′ = es vT

(ε, δ)-differential privacy
Hardt and Price [27]

No assumption
A − A′ = es eT
t

(ε, δ)-differential privacy

Incoherence and SVS

Hardt and Price [27]

A − A′ = es eT
t

(ε, δ)-differential privacy

SVS

Dwork et al. [24]
(ε, δ)-differential privacy
Jiang et al. [31]
(ε, 0)-differential privacy

A − A′ = es vT
No assumptions
A − A′ = es eT
t
No assumption

Multiplicative Error
Additive Error
γ = (1
− α)−2
+√α)(1
√
−2
m+
n+α
e
ζ =O
3/2
(1−α)

ε

γ 
= (1 + α)2 (1 − α)−4 
√
√
kα−1 ln(1/δ)+ m+ n
e
ζ=O
ε(1−α)3
γ=1

ζ = cλ1 , where λ1 = Ω

e
ζ=O

e
ζ=O



nk3
εc6

γ = poly(k)

p
e
ζ = O k 2 ε−1 (m + n)
γ=1
 √

kµ log d log(log dσk /(σk −σk+1 ))
ε(σk −σk+1 )

σ1

 √
σ1



γ=1



kd log d log(log(d)σk /(σk −σk+1 ))
ε(σk −σk+1 )

γ=1
e (k √n/ε)
ζ =O
γ=1

ζ = O nε−1 log n



Table 1: 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 d = m + n).

space required) compared to the turnstile update model even in the non-private setting as
illustrated by Clarkson and Woodruff [10].

1.6

Related Works

Low-rank approximation of large data-matrices has received a lot of attention in the recent past in
the private as well as the non-private setting. In what follows, we give a brief exposition of those
that are most relevant to this work.
In the private setting, previous works have either used random projection [10, 33, 47] or random
sampling (at a cost of a small additive error) to give low-rank approximation [3, 16, 18, 13, 25, 44,
45]. Many of the latter algorithms were improved independently by Deshpande and Vempala [14]
and Sarlos [47]. Subsequent works [11, 38, 40, 42] achieved a run-time that depends linearly on the
input sparsity of the matrix. In a series of works, Clarkson and Woodruff [10, 11] showed space
lower bounds and almost matching space algorithms. Recently, Boutsidis et al. [7] gave the first
space-optimal algorithm for low-rank approximation, but they do not optimize for run-time.
In the private setting, LRA has been studied under a privacy guarantee called differential privacy.
Differential privacy was introduced by Dwork et al. [20]. The Gaussian variant of this basic sanitizer
was proven to preserve differential privacy by [19] in a follow-up work. Since then, many algorithms
for preserving differential privacy have been proposed in the literature [22]. All these mechanisms
have a common theme: they perturb the output before responding to queries. Recently, Blocki et
8

al. [5] and Upadhyay [51] took a complementary approach. They perturb the input reversibly and
then perform a random projection of the perturbed matrix.
Blum et al. [6] first studied the problem of differentially private LRA in the Frobenius norm.
This was improved by Hardt and Roth [28] under the low coherence assumption. Upadhyay [52]
later made it a single-pass. Differentially-private LRA has been studied in the spectral norm as
well by many works [9, 35, 29, 27]. Kapralov and Talwar [35] and Chaudhary et al. [9] studied the
spectral LRA of a matrix by giving a matching upper and lower bounds for privately computing the
top k eigenvectors of a matrix with pure differential privacy (i.e., δ = 0). In subsequent works Hardt
and Roth [29] and Hardt and Price [27] improved the approximation guarantee with respect to the
spectral norm by using robust private subspace iteration algorithm. Recently, Dwork et al. [24] gave
a tighter analysis of Blum et al. [6] to give an optimal approximation to the right singular space,
i.e., they gave a LRA for the covariance matrix.
The literature on non-private algorithms that makes few passes over the input matrix is so
extensive that we cannot hope to cover it in any detail here. In the private setting, Dwork et
al. [21] first considered streaming algorithms with privacy under the model of pan-privacy, where
the internal state is known to the adversary. They gave private analogues of known sampling based
streaming algorithms to answer various counting tasks, like estimating distinct elements, cropped
means, number of heavy hitters, and frequency counts. This was followed by results on online
private learning [24, 30, 50].

2

Notations and Previous Known Results Used in This Paper

We let N to denote the set of natural numbers. We use bold-face capital letters to denote matrices
and bold-face 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 its best k-rank approximation by [A]k , its
Frobenius norm by kAkF , and its spectral norm by kAk2 . 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 have orthonormal 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 det(A) to denote its determinant. 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. Given a random variable x, we denote by N (µ, ρ2 ) the fact that x
has a normal Gaussian distribution with mean µ and variance ρ2 .
Let α, β > 0. A distribution D over p × n random matrices satisfies (α, β)-Johnson-Lindenstrauss
property (JLP) if, for any unit vector x ∈ Rn , we have (1 − α) ≤ kΦxk22 ≤ (1 + α) with
probability 1 − β over Φ ∼ D. A distribution D of p × m matrices satisfies (α, β)-subspace
embedding for a matrix A ∈ Rm×n if, for all x ∈ Rn , with probability 1 − β over Φ ∼ D,
(1 − α)kAxk2 ≤ kΦAxk2 ≤ (1 + α)kAxk2 .
Lemma 10. (Clarkson and Woodruff [11]) Let B1 and B2 be arbitrary matrices with m rows such
that B1 has rank-r. Let D be a distribution over p × m random matrices that satisfies the (α, β)subspace embedding for B1 . Then there exists a p = Θ(α−2 ) such that, with probability at least
1 − β over Φ ∼ D,
T
T
2
2
2
2
kBT
1 Φ ΦB2 − B1 B2 kF ≤ α kB1 kF kB2 kF .

The tuple (α, β) is called the error parameters.
9

p

Initiialization.
Let η := max k 2 , 1/α , ρ :=
(1 + α) ln(1/δ)/ε, t =
O(ηα−1 log(k/α) log(1/δ)), and v = O(ηα−3 log(t/α) log(1/δ)). Sample N1 ∼ N (0, ρ2 )m×t
and N2 ∼ N (0, ρ2 )v×n Let Φ ∈ Rn×t
√ be such that Φ ∼ DR satisfies the statement
of Lemma 10 for the error parameters ( α/k, δ). Let S ∈ Rv×m such that S ∼ DA satisfies
b and an all zero v × n matrix Z.
b Publish S
(α2 , δ)-JLP. Initialize all m × t zero matrix Y
and Φ. N1 and N2 are private matrices.
Update rule and computing the factorization. Suppose at time τ , the stream is
(iτ , jτ , sτ ), where (iτ , jτ ) ∈ [m] × [n]. Let Aτ be a matrix with the only non-zero entry sτ
b ← Y
b + Aτ Φ and
in the position (iτ , jτ ). Update the matrices by the following rule: Y
b
b
Z ← Z + SAτ .
Once the matrix is streamed, we follow the following steps.

eΣ
eV
e T of SU ∈ Rv×t , where U ∈ Rm×t is
1. Compute the singular value decomposition U
b + N1 ).
a matrix whose columns are an orthonormal basis for the column space of (Y

eΣ
e †U
e T [U
eU
e T (Z
b + N2 )]k ∈ Rt×n . Let
2. Compute the singular value decomposition of V
′ ′ ′T
it be U Σ V .
3. Output Uk := UU′ , Σk := Σ′ and Vk := V′ . Let Mk = Uk Σk VkT .

Figure 1: Differentially private Low-rank Factorization (Spectal-LRF)

3

Differentially Private Algorithm for Spectral LRF in the Turnstile Model

In this section, we present our space-efficient private algorithm for LRF under Priv1 with respect
to the spectral norm in the turnstile update model. Our privacy level, Priv1 , is stronger than
that considered by previous (ε, δ)-differentially private algorithms [24, 29, 27]. Our algorithm
formalizes the ideas mentioned in Section 1.4. In particular, we show that we can compute a set of
k-orthonormal basis vectors that approximates the top-k left singular space of the private matrix in
the turnstile update model. The details of our algorithm Spectral-LRF is presented in Figure 1.
We prove the following bound about Spectral-LRF.
Theorem 11. Let m, n ∈ N and ε, δ be the input parameters with m ≥ n. Let k be the desired
rank of the factorization. Let α ∈ (0, 1) be an arbitrary constant. Given an m × n matrix A in the
turnstile update model, the algorithm Spectral-LRF, presented in Figure 1, satisfies the following
properties:

1. Let η = max k2 , 1/α . Then Spectral-LRF uses O((mηα−1 + nηα−3 ) log(k/α2 ) log(1/δ))
space.
2. Spectral-LRF is (ε, δ)-differentially private under Priv1 .
3. With probability at least 9/10 over the coin tosses of Spectral-LRF,
√


√
m + n + α−2 p
(1 + α)
∆
(A)
+
O
log(1/δ)
,
kA − Mk k2 ≤
k
(1 − α)2
(1 − α)3/2 ε
10

where Mk = Uk Σk VkT .
When m < n, we can get similar bounds with the roles of m and n reversed and by using AT
in Figure 1. The key technical point in the proof is to prove that U is indeed a good approximation
to the top-k left singular vectors of A and S has the property that, simultaneously for all matrices
(1+α)
k(UX − A)k2 .
X of appropriate dimensions, kS(UX − A)k2 ≤ (1−α)
Proof of Theorem 11. The space complexity of the algorithm is straightforward from the choice
of v and t. The proof of correctness consists of two main lemmas (Lemma 12 and Lemma 15).
In Lemma 12, we bound kMk − Ak2 by kA − [A]k k2 and two additive terms. In Lemma 15, we
bound the two additive terms.
b
For all our correctness proofs, we make a standard assumption that δ ≪ 1/100. Let Y = Y+N
1,
†
b
b
b
Z = Z + N2 , and B = A + S N2 for Y, Z, S, N1 , N2 as in Figure 1.

Lemma 12. Let Uk , Σk , Vk be the output of the algorithm Spectral-LRF presented in Figure 1
such that Mk := Uk Σk VkT . Then with probability 1 − O(δ) over Φ ∼ DR and S ∼ DA ,
kMk − Ak2 ≤

2kN2 S† k2 1 + α
(1 + α)
†
T
+
kN1 ([V]T
kA
−
[A]
k
+
2
k
k Φ) [V]k k2 .
(1 − α)2
1−α
1−α

Proof. We prove Lemma 12 by proving two seperate claims. Claim 13 shows that U is a “faithful”
representation of the top-k left singular vectors of [A]k and Claim 14 shows that S satisfies the
required properties with the choice of error parameters.
Claim 13. Let A be the input matrix. Let Φ ∼ DR be a random matrix that satisfies Lemma 10
√
with error parameters ( α/k, δ) with respect to a rank-k matrix [V]k . Then with probability 1 − δ
over Φ ∼ DR ,
min

X,r(X)≤k

kUX − Bk2 ≤

(1 + α)
†
†
T
∆k (A) + kN1 ([V]T
k Φ) [V]k k2 + kS N2 k2 .
(1 − α2 )

Before, we prove Claim 13, we prove some auxiliary results. Let us denote by [U]k [Σ]k [V]T
k the
SVD of [A]k . We first note that U is an orthonormal basis for the column space of Y, i.e.,
min

X,r(X)≤k

kUX − Bk2 ≤

min

X,r(X)≤k

kYX − Bk2 .

(4)

√
We also note that the choice of t allows Φ to satisfy Lemma 10 with error parameters ( α/k, δ) [11].
Therefore, in order to show that U approximates the top-k left singular vectors of the matrix A,
we need to find an appropriate matrix X such that kYX − Ak2 is bounded by a multiplicative
factor of kA − [A]k k2 . Towards this goal, consider the following two optimization problems:
min kΦT ([V]k X − AT )k2
X

and

min k[V]k X − AT k2 .
X

with
e := argmin kΦT ([V]k X − AT )k2
X
X

b := argmin k[V]k X − AT k2
X
X

11

(5)

as one of the solutions. We first give the sketch of the proof. Our goal is to show that
e − AT k2 ≤ (1 − α)−1 k[V]k X
b − AT k2 .
k[V]k X

(6)

This would give us Claim 13 after substituting the value of B and Y because of the following
argument.
b minimizes Problem 2, X = [Σ]k [U]T would only increase the value of k([V]k X−AT )k2 .
Since X
k

That is,

b − AT k2 = min k([V]k X − AT )k2
k[V]k X
X

≤ kAT − [V]k [Σ]k [U]T
k k2

= ∆k (A).

(7)

Now since Problem 1 is a minimization problem over all possible matrices X, using Theorem 44
e = (ΦT [V]k )† ΦT AT . Furthermore,
and the singular value decomposition of ΦT [V]k , we get X
T
†
r([V]k (Φ [V]k ) ) ≤ k. This implies that
min kUX − Ak2 ≤ min kAΦX − Ak2

r(X)≤k

r(X)≤k

≤ kAΦ([V]k (ΦT [V]k )† )T − Ak2
e − AT k2 .
= k[V]k X

(8)

We get the desired result by combining equation (6), equation (7), equation (8), and substituting
b
the value of B = A+S† N2 and Y = A+N
1 . Therefore, the key to our proof is to prove equation (6).
Proving equation (6). We now prove equation (6). Using the sub-additivity of the spectral
norm, we have
e 2 ≤ kAT − [V]k Xk
b 2 + k[V]k (X
e − X)k
b 2.
kAT − [V]k Xk

The first term in the above expression has the form that we desire. Therefore, towards the goal
e − X)
b and D = [V]k (X
e − X).
b
e − X)k
b 2 . Let C = [V]T [V]k (X
we set forth, we need to bound k[V]k (X
k
T
T
It is easy to see that C C = D D; therefore kDk2 = kCk2 . This implies that instead of D if we
T
T
e
bound C, then we are done. We first make an observation that [V]T
k ΦΦ (A −[V]k X) = 0 because
T
T
T
T
†
T
I − Φ [V]k (Φ [V]k ) is a projection on to the space orthogonal to [V]k Φ and [V]T
k ΦΦ (A −
e equals
[V]k X)
T T
T
T
† T T
[V]T
k Φ(Φ A − Φ [V]k (Φ [V]k ) Φ A ) = 0.

(9)

Now, we return to the proof of equation (6). The sub-additivity and sub-multiplicativity of the
spectral norm gives us the following:
T
T
T
kCk2 = k[V]T
k ΦΦ [V]k C − [V]k ΦΦ [V]k C + Ck2

T
T
T
≤ k[V]T
k ΦΦ [V]k Ck2 + k([V]k ΦΦ [V]k − I)Ck2

T
T
≤ k[V]T
k ΦΦ [V]k Ck2 + k(ΦΦ − I)k2 kCk2 .

12

The choice of the dimension of Φ allows us to use the result of Clarkson and Woodruff [10]
(Lemma 43).
T
kCk2 ≤ (1 − α2 )−1 k[V]T
k ΦΦ [V]k Ck2

T
≤ (1 − α2 )−1 k[V]T
k ΦΦ [V]k CkF
e − X)
b + [V]T ΦΦT (AT − [V]k X)k
e F
= (1 − α2 )−1 k[V]T ΦΦT [V]k (X

= (1 −

≤ (1 −

k
T
b F
α ) k[V]k ΦΦT (AT − [V]k X)k
√
b F / k.
α2 )−1 αk(AT − [V]k X)k

k

2 −1

b 2,
≤ (1 − α2 )−1 αk(AT − [V]k X)k

the equality follows from equation (9)), the second and last inequality follows from Fact 40.
In the above inequalities, we were able to apply Lemma 10 because [V]k is a rank-k matrix and
√
Φ satisfies ( α/k, δ)-subspace embedding with respect to [V]k . Now, from the sub-additivity of
the spectral norm,
e 2 ≤ kAT − [V]k Xk
b 2 + k[V]k (X
e − X)k
b 2
kAT − [V]k Xk

b 2
≤ (1 + α − α2 )(1 − α2 )−1 kAT − [V]k Xk
b 2
≤ (1 + α)(1 − α2 )−1 kAT − [V]k Xk

b 2.
= (1 − α)−1 kAT − [V]k Xk

(10)

This gives us the desired expression stated in equation (6).

Proof of Claim 13. We now complete the proof of Claim 13. We follow the sketch of the proof
b we have
given earlier. By the definition of X,
b 2 = min k[V]k X − AT k2 ≤ k[V]k [Σ]k [U]T − AT k2 = ∆k (A)
kAT − [V]k Xk
k
X

e
by setting X = [Σ]k [U]T
k . Using equation (6), substituting the value of X, taking the transpose,
and the fact that the spectral norm is preserved under transpose, we have with probability 1 − δ
over Φ ∼ DR ,
−1
†
T
kAΦ([V]T
k Φ) [V]k − Ak2 ≤ (1 − α) ∆k (A).

(11)

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

X,r(X)≤k

†
T
k(YX − Bk2 ≤ kY([V]T
k Φ) [V]k − Bk2
†
T
T
†
T
= kAΦ([V]T
k Φ) [V]k + N1 ([V]k Φ) [V]k − Bk2

†
†
T
T
†
T
= kAΦ([V]T
k Φ) [V]k + N1 ([V]k Φ) [V]k − A − S N2 k2
†
T
≤ kAΦ([V]T
k Φ) [V]k − Ak2

†
†
T
+ kN1 ([V]T
k Φ) [V]k k2 + kS N2 k2

13

(12)

Combining equation (11) and equation (12), we have with probability 1 − δ over Φ ∼ DR ,
min

X,r(X)≤k

†
†
T
kYX − Bk2 ≤ (1 − α)−1 ∆k (A) + kN1 ([V]T
k Φ) [V]k k2 + kS N2 k2 .

(13)

†
T
The above expression relates minX,r(X)≤k kYX−Bk with (1−α)−1 ∆k (A), kN1 ([V]T
k Φ) [V]k k2 ,
and kS† N2 k2 . Combining equation (13) and equation (4), we have with probability 1 − δ over
Φ ∼ DR ,

min

X,r(X)≤k

†
T
†
kUX − Bk2 ≤ (1 − α)−1 ∆k (A) + kN1 ([V]T
k Φ) [V]k k2 + kS N2 k2 .

(14)

This completes the proof of the Claim 13.
†
T
†
Note that the terms kN1 ([V]T
k Φ) [V]k k2 and kN2 S k2 are due to the addition of Gaussian
matrices to preserve privacy. We later bound them in Lemma 15. We next bound that multiplying
S from the right does not change our bound by a lot. More concretely, we prove the following
claim.

e k = argminX,r(X)=k kS(UX − B)k2 .
Claim 14. Let U, B, A, S, N1 , and N2 be as above, and let X
2
Let DA be a distribution that satisfies (α , δ)-JLP. Then with probability 1 − 3δ over S ∼ DA and
Φ ∼ DR , we have
1−α
1
†
T
e k − B)k2 ≤
k(UX
∆k (A) + kN2 S† k2 + kN1 ([V]T
k Φ) [V]k k2 .
1+α
(1 − α)

(15)

b k = argminX,r(X)≤k k(UX−
Proof. First note that the choice of v allows S to satisfy (α2 , δ)-JLP [11]. Let X
b k − Bk2 in terms of kUX
e k − Bk2 . We give an even stronger result
B)k2 . We want to bound kUX
that states that, simultaneously for all X, kS(UX − B)k2 is bounded by a multiplicative factor of
kUX − Bk2 .
For this consider the following optimization problem: minX kUX − Bk2 . Since X can have rank
at most the rank of B, using Theorem 44, we have that
b = UT [UUT B] = UT B
X

is a solution to minX kUX − Bk2 . This implies that

b − B) = UT (UUT − I)B = 0.
UT (UX

(16)

Therefore, using sub-additivity and sub-multiplicativity of the spectral norm and (α2 , δ)-JLP of
DA , we have with probability 1 − δ,
b + S(UX
b − B)k2
kS(UX − B)k22 = kSU(X − X)
2
2
b
b
≤ 2(kSU(X − X)k2 + kS(UX − B)k22 )


b 22 + k(UX
b − B)k22
≤ 2(1 + α2 )2 kU(X − X)k


b 2 + k(UX − B)k2
≤ 2(1 + α2 )2 kU(X − X)k
2
2


b
= 2(1 + α2 )2 kUT U(X − X)


b − B)k2 + k(UX − B)k2
+ 2(1 + α2 )2 UT (UX
2
2
≤ (4 + 12α2 )k(UX − B)k22 ,
14

where the second equality follows from equation (16), the second inequality follows from Lemma 42,
b and the last inequality follows because α < 1.
the third inequality follows from the definition of X,
This in particular implies that
kS(UX − B)k22 − 4k(UX − B)k22 ≤ 12α2 k(UX − B)k22 .

Taking square root and the fact that
p
p
|a − b| ≤ (a + b)(a − b) = a2 − b2

for positive integers a and b, this gives the inequality

√
|kS(UX − B)k2 − 2k(UX − B)k2 | ≤ 2 3αk(UX − B)k2
By rescaling the value of α, we have the following:
2(1 − α)k(UX − B)k2 ≤ kS(UX − B)k2

≤ 2(1 + α)k(UX − B)k2

(17)

e k and X
b k along with equaWe now return to the proof of Claim 14. Using the definitions of X
tion (17), we have the following set of inequalities:
min

X,r(X)=k

b k − Bk2
kUX − Bk2 = kUX

b k − B)k2
≥ (2 + 2α)−1 kS(UX
≥ (2 + 2α)−1

min

X,r(X)≤k

kS(UX − B)k2

e k − B)k2
= (2 + 2α)−1 kS(UX
1−α
e k − B)k2 .
k(UX
≥
1+α

(18)

Combining equation (18) with equation (14), we have with probability 1 − 3δ over Φ ∼ DR and
S ∼ DA ,
1−α
e k − B)k2 ≤ (1 − α)−1 ∆k (A) + kS† N2 k2 + kN1 ([V]T Φ)† [V]T k2 .
k(UX
k
k
1+α

(19)

This completes the proof of Claim 14.

We can now complete the proof of Lemma 12. Since B = A + S† N2 , using sub-additivity of
norm,
e k − Ak2 − kS† N2 k2 ≤ kUX
e k − Bk2 ≤ (1 + α) kA − [A]k k2 + 1 + α (kS† N2 k2 + kN1 ([V]T Φ)† [V]T k2 ).
kUX
k
k
(1 − α)2
1−α

This implies that

e k − Ak2 ≤
kUX

2kS† N2 k2 1 + α
(1 + α)
†
T
+
kN1 ([V]T
kA
−
[A]
k
+
2
k
k Φ) [V]k k2 .
(1 − α)2
1−α
1−α

e =V
eΣ
e †U
e T [U
eU
e T Z]k . Using this
Setting L := SU, R = I, and O := Z Theorem 44 gives that X
e
value of X completes the proof of Lemma 12.
15

Now all that remains to complete the proof of correctness of Theorem 11 are the two expressions
†
†
T
in the additive term: kN1 ([V]T
k Φ) [V]k k2 and kS N2 k2 . We next bound them in Lemma 15.
p
Lemma 15. Let ρ = (1 + α) log(1/δ)/ε and N1 ∼√N (0, ρ2 )m×t . Then with probability 1 − 2δ
−1/2 ( k + √m)) and kN Sk = O(ρ(√v + √n)).
†
T
over Φ ∼ DR , kN1 ([V]T
2
2
k Φ) [V]k k2 = O(ρ(1 − α)
†
T
T
†
T
T
†
T
Proof. We first bound kN1 ([V]T
k Φ) [V]k k2 . Let C = N1 ([V]k Φ) [V]k . Then CΦ = N1 ([V]k Φ) [V]k Φ.
†
Now ([V]k Φ) [V]k Φ is a projection unto a random subspace of dimension

 k. Since every entries
†
T
2
T
e 1 is an m × k
e
of N1 is picked i.i.d. from N (0, ρ ), CΦ = N1 ([V]k Φ) [V]k Φ = N1 0 , where N

matrix with every entries picked i.i.d. from √
N (0, ρ2 ). Using Rudelson and Vershynin [46, Propo√
sition 2.4], we have kCΦk2 = O(ρ( m + k)) with probability 99/100. For our choices of t,
Sarlos [47] showed that, for any matrix D, all the singular values of DΦ lies in between (1 ± α) of
the singular values of D.√This in particular implies that kCΦk2 ≥ (1 − α)1/2 kCk2 , and, therefore,
√
kCk2 ≤ (1 − α)−1/2 O(ρ( k + m)). This completes the proof of Lemma 15. For the second part, if
we instantiate S with a subsampled Hadamard matrices, it is known that it satisfies (α2 , δ)-JLP for
√
√
the values of v. Applying Lemma 34, we have kS† N2 k2 = kN2 k2 = O(ρ( n + v)) using Rudelson
and Vershynin [46] with probability 99/100. This completes the proof of Lemma 15.
Combining Lemma 12 and Lemma 15 completes the correctness proof of Theorem 11. We next
prove the privacy part of Theorem 11.
p
Lemma 16. If ρ = (1 + α) ln(1/δ)/ε, then publishing Yr and Z preserves(2ε, 4δ)-differential
privacy.
Proof. First note that Clarkson and Woodruff [11] showed that for the choice of t and v, with
probability 1 − δ, we have kSDk2F ≤ (1 ± α)kDk2F and kDΦk2F ≤ (1 ± α)kDk2F for all D. Let A
and A′ be two neighboring matrices such that E = A − A′ . Then kSEk2F ≤ (1 + α)kEk2F ≤ (1 + α).
Publishing Z preserves (ε, δ)-differential privacy follows from considering the vector form of the
matrix SA and N2 and applying Theorem 37. Similarly, we use Theorem 37 and the fact that, for
any matrix C of appropriate dimension, kCΦk2F ≤ (1 + α)kCk2F , to prove that publishing AΦ + N1
preserves differential privacy.
Combining Lemma 12, Lemma 15, and Lemma 16 gives Theorem 11.
In the most natural scenarios, k ≪ max {m, n} and α is a small constant. Then we have
(1 − α)−1 ≈ (1 + α). If we scale the value of α appropriately, then we have the following corollary.
Corollary 17. Under the assumptions of Theorem 11 and α ∈ (0, 1) a small constant, given an
m×n matrix A in the turnstile update model, the algorithm Spectral-LRF, presented in Figure 1,
is (ε, δ)-differentially private under Priv1 and outputs a k-rank factorization Uk , Σk , and VkT (with
Mk = Uk Σk VkT ), such that, with probability 9/10 over the coin tosses of Spectral-LRF,
 √

p
√ 
kA − Mk k2 ≤ (1 + α)∆k (A) + O
m + n ε−1 log(1/δ) ,

As another corollary of Theorem 11, when ε → ∞, we get a non-private algorithm that computes
low-rank factorization under turnstile update model with respect to the spectral norm.

16

Corollary 18. Let m, n ∈ N and k be the input parameters. Let α ∈ (0, 1) be a constant. Given
a matrix A ∈ Rm×n in the turnstile update model, there exists an algorithm that outputs a k-rank
factorization Uk , Σk , Vk such that with probability 99/100 over the coin tosses of the algorithm,
kA − Uk Σk VkT k2 ≤ (1 + α)∆k (A).

4

Improving the Space Bound in the Turnstile Model

In this section, we improve the space bound of Spectral-LRF under Priv2 in the turnstile update
model. This privacy level is also stronger than that considered by previous (ε, δ)-differentially
private algorithms, but weaker than that in Section 3. Our algorithm formalizes the ideas mentioned
in Section 1.2. In particular, we show that we can simultaneously compute two sets of k-orthonormal
basis vectors that approximates the top-k left and top-k right singular vectors of the private matrix
in the turnstile update model.
We have to be careful with how we introduce noise to preserve privacy. If we use output
perturbation to compute the sketches Yc = AΦ + N and Yr = ΨA + N′ , then one of the error
†
T
† † ′
terms is kN([A]T
k Φ) (ΨAΦ([A]k Φ) ) N k2 . This term can cause the additive error to be Ω(n)
if the top singular values of A is 1/n. If we only use input perturbation of the sketches followed
by a multiplication by Gaussian matrices as in [5, 52, 53], the multivariate Gaussian distribution
corresponding to one of the sketches is not defined as one of the sketches is not a full rank matrix.
Moreover, we cannot guarantee that the kernel space are the same for neighboring matrices A and
A′ . Therefore, the privacy proof would not follow. Our algorithm uses both the input perturbation
with a careful choice of parameters and output perturbation to the other two sketches. This
preserves privacy as well as keep the additive error bounded. We show the following theorem.
Theorem 19. Let m, n, k ∈ N and ε, δ be the input
∈ (0, 1) be an arbitrary
p parameters. Let α p
constant,√κ = (1 + α)/(1 − α), σmin = 16 ln(1/δ) tκ ln(4/δ)/ε, ρ1 = (1 + α) ln(1/δ)/ε, and
ρ2 = ρ1 1 + α. Given an m × n matrix A in the turnstile update model, the algorithm LowSpace-LRF, presented in Figure 2, satisfies the following properties:

1. Let η = max k2 , 1/α . Then Spectral-LRF uses O((m + n)ηα−1 log(k/α) log(1/δ)) space.
2. Spectral-LRF is (ε, δ)-differentially private under Priv2 .

3. With probability at least 9/10 over the coin tosses of Spectral-LRF,
 −1

√
√ 

kα ln(1/δ) + m + n p
(1 + α)2
∆
(A)
+
O
kMk − A 0 k2 ≤
ln(1/δ)
.
k
(1 − α)4
ε(1 − α)3
For the sake of simplicity, we present the algorithm when m ≤ n. When m > n, we change the
T

algorithm in Figure 2 as follows: (i) use AT instead of A, (ii) use 0 σIn instead of 0 σIm
b c, Y
b r and Z,
b (iii) the matrices S, T, Φ, and Ψ are picked using the same distribution
to initialize Y
but with appropriate dimensions to allow matrix multiplication.
The space complexity of the algorithm is straightforward from the choice of t and v. We first
prove part 3 of Theorem 19. Our proof consists of few main lemmas
(Lemma 20, Lemma 21,

b 2 and a fixed
Lemma 25, and Lemma 24). Lemma 20 bounds kMk − A 0 k2 by kMk − Ak
b 2 by kA
b − [A]
b k k2 and two additive terms. Lemma 25
additive term. Lemma 21 bounds kMk − Ak
17

p

Initiialization.
Let η := max k 2 , 1/α , ρ1 :=
(1 + α) ln(1/δ)/ε, t =
−3
O(ηα−1 log(k/α) log(1/δ)),
v
=
O(ηα
log(t/α)
log(1/δ)),
κ
=
(1 + α)/(1 − α), and
p
p
σmin = 16 ln(1/δ) tκ ln(4/δ)/ε, and ρ2 := (1 + α)ρ1 . Set A = 0 σmin Im . Sample N1 ∼ N (0, ρ21 )t×(m+n) and N2 ∼ N (0, ρ22 )v×v . Let Φ ∈ R(m+n)×m , Ψ ∈ Rt×m
p be such
that Φ, Ψ ∼ DR satisfies the statement of Lemma 10 for the error parameter α/k. Let
S ∈ Rv×m , T ∈ R(m+n)×v such that S, T satisfies (α2 , δ)-JLP. Sample Ω ∼ N (0, 1)m×t and
cc = AΦ
b ∈ Rm×t , Y
b r = ΨA ∈ Rt×(m+n) , and Z
b = SAT ∈ Rv×v .
b = √1 ΦΩ. Initialize Y
Φ
t

Update rule and computing the factorization. Suppose at time τ , the stream is
(iτ , jτ , sτ ), where (iτ , jτ ) ∈ [m] × [n]. Let Aτ be an m × (m + n) matrix with the only
bc ←
non-zero entry sτ in the position (iτ , jτ ). Update the matrices by the following rule: Y
b
b
b
b
b
b
Yc + Aτ Φ, Yr ← Yr + ΨAτ and Z ← Z + SAτ T.

Once the matrix is streamed, we follow the following steps.

1. Compute a matrix U ∈ Rm×t whose columns are an orthonormal basis for the column
b c.
space of Y

2. Compute a matrix V ∈ R(m+n)×t whose rows are an orthonormal basis for the row
b r + N1 .
space of Y
e T be the SVD of TT V ∈ Rv×t .
e tV
e T be the SVD of SU ∈ Rv×t . Let U
e tΣ
e sV
e sΣ
3. Let U
t
s

e eT e e† eT
e †U
eT e eT b
e sΣ
4. Let U′ Σ′ V′T be the SVD of V
s s [Us Us (Z + N2 )Vt Vt ]k Vt Σt Ut .
5. Output Uk = UU′ , Σk := Σ′ and Vk := VV′ . Let Mk = Uk Σk VkT .

Figure 2: Differentially private Low-rank Factorization With Improved Space (Low-Space-LRF)

b − [A]
b k k2 in the terms of kA − [A]k k2 and a fixed additive term. Lemma 24 bounds
bounds kA
the two additive terms in Lemma 21 completing the proof.
b
For all our correctness proofs, we make a standard assumption that δ ≪ 1/100. Let Z := Z+N
2,
†
†
b
b
b
Yc := Yc , Yr := Yr + N1 , and B = A + S N2 T , where all the variables on the right hand side
of the expressions are as in Figure 2.
b 2 and a small additive term. The
We start by proving a bound on kMk − Ak2 by kMk − Ak
following lemma provides such a bound.

b = A σmin Im for σmin defined in Figure 2.
Lemma 20. Let A be an m×n input matrix, and let A
Let Mk = Uk Σk VkT , where Uk , Σk , Vk is the factorization outputted by Low-Space-LRF. Then

b 2 + σmin .
kMk − A 0 k2 ≤ kMk − Ak


b = A σmin Im , the lemma is immediate from the following.
Proof. Since A




b 2,
kMk − A 0 k2 − σmin kIm k2 ≤ kMk − A 0 − 0 σmin I k2 = kMk − Ak

where the first inequality follows from the sub-additivity of the spectral norm.

b 2 by kA
b − [A]
b k k2 and some additive terms.
We next prove a bound on kMk − Ak
18

Lemma 21. Let Mk := Uk Σk VkT , where Uk , Σk , Vk is the factorization outputted by Low-SpaceLRF presented in Figure 2. Then with probability 1 − O(δ) over Φ, Ψ ∼ DR and S, T ∼ DA ,
2
†
2
b − [A]
b k k2 + 2(1 + α )kN2 S k2 +
b 2 ≤ (1 + α) kA
kMk − Ak
(1 − α)4
(1 − α)2



1+α
1−α

2

†
T
kN1 ([V]T
k Φ) [V]k k2 .

Proof. Our proof consists of two main claims (Claim 22 and Claim 23). Claim 22 shows that U and
V are “faithful” representations of the top-k left and right singular vectors of [A]k and Claim 23
shows that S and T satisfies the required properties with the choice of error parameters.
Claim 22. Let A be the input matrix. Let Φ ∼ DR be a random matrix that satisfies Lemma 10
√
with error parameters ( α/k, δ) with respect to [V]k and Ψ ∼ DR satisfies Lemma 10 with error
√
T Φ)† . Then with probability 1 − 2δ over the choices
b
parameters ( α/k, δ) with respect to AΦ([V]
k
of Φ and Ψ,
min

X,r(X)≤k

†
†
b − [A]
b k k2 + kAΦDN
b
kUXVT − Bk2 ≤ (1 − α)−2 kA
1 k2 + kS N2 T k2 .

b
Proof. Let us denote by [U]k [Σ]k [V]T
k the SVD of [A]k . By construction, U is an orthonormal
basis for the column space of Yc and V is an orthonormal basis for the row space of Yr , i.e.,
min

X,r(X)≤k

kUXVT − Bk2 ≤

min

X,r(X)≤k

kYc XYr − Bk2 .

(20)

We also note that the choice of t allows Φ and Ψ to satisfy Lemma 10 with error parameters
√
( α/k, δ) [11]. Therefore, in order to show that the matrix U approximates the top-k left singular
b and V approximates the top-k right singular vectors of the matrix A,
b we
vectors of the matrix A
b 2 is bounded by (1 − α)−2 kA
b − [A]
b k k2 up to some
need to find a matrix X such that kYc XYr − Ak
additive terms. Towards this goal, first consider the following two optimization problems:
b T )k2
min kΦT ([V]k X − A
X

with

and

b T )k2 .
min k([V]k X − A
X

(21)

e := argmin kΦT ([V]k X − A
b T )k2
X
X

b := argmin k([V]k X − A
b T )k2
X
X

being one of the solutions of equation (21).
b
Recall that Φ satisfies Lemma 10 with respect to [V]k . Therefore, if we substitute A by A
e −A
b T k2 ≤ (1 − α)−1 k([V]k X
b −A
b T )k2 , where X
e = (ΦT [V]k )† ΦT A
b T.
in equation (6), then k[V]k X
This is the same as
−1
†
T
T
b
bT
b
eT T b
b
kAΦ([V]
k Φ) [V]k − Ak2 = kX [V]k − Ak2 ≤ (1 − α) k([V]k X − A )k2

T Φ)† . The matrix C has a rank at most k and the above equation
b
Define a matrix C := AΦ([V]
k
can be rewritten as
−1
b
b
bT
kC[V]T
k − Ak2 ≤ (1 − α) k([V]k X − A )k2 .

19

(22)

Now consider the following optimization problem:
b 2
min kΨ(CX − A)k
X

b 2.
min k(CX − A)k

and

X

(23)

b Theorem 44 and a singular value decomposition of ΨC, we have
Setting L := ΦC and A = A
e ′ := (ΨC)† ΨA
b = argmin kΨ(CX − A
b T )k2 .
X
X

Recall that Ψ satisfies Lemma 10 with respect to C. Therefore, using equation (6) on problems (23), we have
′

e − Ak
b 2 ≤ (1 − α)−1 min kCX − Ak
b 2
kCX
X

b
kC[V]T
k − Ak2
b −A
b T )k2
≤ (1 − α)−2 k([V]k X
−1

≤ (1 − α)

b T )k2
= (1 − α)−2 min k([V]k X − A
X

b
k[U]k [Σ]k [V]T
k − Ak2
b k − Ak
b 2.
= (1 − α)−2 k[A]
−2

≤ (1 − α)

(24)

In the above, the third inequality follows from using equation (22) and fourth follows from the
b
definition of X.
†
† †
†
b
e′
b
b
Let D = ([V]T
k Φ) (ΨAΦ([V]k Φ) ) , i.e., CX = AΦDΨA. Since ([V]k Φ) [V]k has rank at
b + N1 , with probability 1 − δ over Φ ∼ DR ,
most k and Y = ΨA
min

X,r(X)≤k

b
b + AΦDN
b
kYc XYr − Bk2 ≤ kAΦDΨ
A
1 − Bk2

†
†
b
b + AΦDN
b
b
= kAΦDΨ
A
1 − A − S N2 T k2
†
†
b
b − Ak
b 2 + kAΦDN
b
≤ kAΦDΨ
A
1 k2 + kS N2 T k2
†
†
e ′ − Ak
b 2 + kAΦDN
b
≤ kCX
1 k2 + kS N2 T k2

(25)

Combining equation (24) and equation (25), we have with probability 1 − 2δ over the choice of
Φ and Ψ,
†
†
b − [A]
b k k2 + kAΦDN
b
min kYc XYr − Bk2 ≤ (1 − α)−2 kA
1 k2 + kS N2 T k2 .

(26)

†
†
b − [A]
b k k2 + kAΦDN
b
min kUXVT − Bk2 ≤ (1 − α)−2 kA
1 k2 + kS N2 T k2 .

(27)

X,r(X)≤k

Combining equation (26) and equation (20), we have with probability 1 − 3δ over Φ and Ψ,
X,r(X)≤k

This completes the proof of Claim 22.

b
We would have been done if we had not generated a noisy version of the sketch SAT.
The next
claim bounds the effect of generating this sketch.
20

b S, N1 , and N2 be as above, and let X
e k = argminX,r(X)=k kS(UXVT −
Claim 23. Let U, B, A,
B)Tk2 . Let DA be a distribution that satisfies (α2 , δ)-JLP. Then with probability 1 − 6δ over
S, T ∼ DA and Φ, Ψ ∼ DR , we have


1−α 2
e k VT − B)k2 ≤ (1 − α)−2 kA
b − [A]
b k k2 + kS† N2 T† k2 + kAΦDN
b
k(UX
1 k2 .
1+α

Proof. Note that the choice of v allows S and T to satisfy (α2 , δ)-JLP.
b k = argminX,r(X)≤k k(UXVT − B)k2 . We want to bound kUX
b k VT − Bk2 in terms of
Let X
e k VT − Bk2 . Using the definitions of X
e k and X
b k along with equation (17), we have
kUX
min

X,r(X)=k

b k VT − Bk2
kUXVT − Bk2 = kUX

b k VT − B)k2
≥ (2 + 2α)−1 kS(UX
b k VT − B)Tk2
≥ (2 + 2α)−2 kS(UX

≥ (2 + 2α)−2

min

X,r(X)≤k

kS(UXVT − B)Tk2

e k VT − B)Tk2
= (2 + 2α)−1 kS(UX


1−α 2
e k VT − B)k2 .
≥
k(UX
1+α

(28)

Combining equation (28) with equation (27), we have with probability 1 − 3δ over Φ ∼ DR and
S ∼ DA ,


1−α 2
e k VT − B)k2 ≤ (1 − α)−2 kA
b − [A]
b k k2 + kS† N2 T† k2 + kAΦDN
b
k(UX
(29)
1 k2 .
1+α

This completes the proof of Claim 23.

b + S† N2 T†
We can now complete the proof of Lemma 21. Since B = A

e k VT − Ak
b 2 − kS† N2 T† k2 ≤ kUX
e k VT − Bk2
kUX
This implies that

(1 + α)2 b
b k k2 +
≤
kA − [A]
(1 − α)4



1+α
1−α

2

b
(kS† N2 T† k2 + kAΦDN
1 k2 ).

2
2
† †
e k VT − Ak
b 2 ≤ (1 + α) kA
b − [A]
b k k2 + 2(1 + α )kN2 S T k2 +
kUX
(1 − α)4
(1 − α)2



1+α
1−α

2

b
kAΦDN
1 k2 .

Setting O := Z, L := SU and R := VT T in the statement of Theorem 44, we have
ek = V
e sΣ
e †U
eT e eT e eT e e† eT
X
s s [Us Us ZVt Vt ]k Vt Σt Ut

is one of the candidate solutions to

argmin kS(UXVT − B)k2 .

X,r(X)=k

e k completes the proof of Lemma 21.
Using this value of X
21

b
Lemma 21 contains two additive terms kS† N2 T† k2 and kAΦDN
1 k2 . We next bound both
these terms.
p
Lemma 24. Let ρ = (1 + α) log(1/δ)/ε and N1 ∼ N (0, ρ2 )(m+n)×t . Then with probability 1 − 2δ
√
√
−1/2 ( k + m + n)) and kS† N T† k = O(ρ √v).
b
over Φ ∼ DR , kAΦDN
1 k2 = O(ρ1 (1 − α)
2
2
2
b
Proof. Let C = AΦDN1 . Then
T
†
† †
b
b
ΨC = ΨAΦ([V]
k Φ) (ΨAΦ([V]k Φ) ) N1 .

b
Now ΨAΦD
is a projection unto a random subspace of dimension at most k. Since every entries
e 1 , where N
e 1 is an m × k matrix with every entries
of N1 is picked i.i.d. from N (0, ρ2 ), ΨC = N
2
picked
√ N (0, ρ ). Using Rudelson and Vershynin [46, Proposition 2.4], we have kΨCk2 =
√ i.i.d. from
O(ρ( m + n + k)) with probability 99/100. For our choices of t, Sarlos [47] showed that, for any
matrix E, all the singular values of ΨE lies in between (1 ± α) of the singular values
E. This in
√ of √
1/2
−1/2
particular implies that kΨCk2 ≥ (1−α) kCk2 . That is, kCk2 = (1−α)
O(ρ1 ( k + m + n)).
For the second part, if we instantiate S with a subsampled Hadamard matrices, it is known that it
satisfies (α2 , δ)-JLP for the values of v. Applying Lemma 34 twice, we have kS† N2 T† k2 = kN2 k2 =
√
O(ρ2 v) using Rudelson and Vershynin [46] with probability 99/100. This completes the proof
of Lemma 24.
b − [A]
b k k2 in terms of kA − [A]k k2 .
We finally compute an upper bound on kA
b Let σ1 , · · · , σd be the singular values
Lemma 25. Let d be the maximum of the rank of A and A.
b
b
b k k2 ≤ kA − [A]k k2 + σmin .
of A and σ
b1 , · · · , σ
bd be the singular values of A. Then kA − [A]

b = A 0 +
Proof. We first prove that |σi − σi′ | ≤ σmin for all 1 ≤ i ≤ d.  We can write A
0 σmin Im . By construction, all the singular values of 0 σmin Im are σmin ; therefore, Theorem 39
b − [A]
b k k2 = σ
implies that |σi − σi′ | ≤ σmin for all 1 ≤ i ≤ d. In particular, since kA
bk+1 and
kA − [A]k k2 = σk+1 , this implies that |b
σk+1 − σk+1 | ≤ σmin . The lemma follows.

Combining Lemma 20, Lemma 21, Lemma 25, and Lemma 24 completes the proof of part 3
of Theorem 19 after noting that α ∈ (0, 1). We next prove part 2 of Theorem 19. This is essentially
the same as in Upadhyay [54]. We include it for the sake of completion.
Lemma 26. If σmin , ρ1 and ρ2 be as in Theorem 19, then the algorithm presented in Figure 2, is
(3ε, 6δ)-differentially private.
We prove the lemma when m ≤ n. The case for m ≥ n is analogous after inverting the roles of
b
b
b′
Φ and Ψ. Let A and A′ be two neighboring matrices, i.e., E = A − A′ = uvT
 . Then A and A ,
′
b
b
constructed by Low-Space-LRF, has the following property: A = A + E 0 .
p
Claim 27. If
pρ1 = (1 + α) ln(1/δ)/ε, then publishing Yr preserves(ε, 2δ)-differential privacy. If
ρ2 = (1 + α) ln(1/δ)/ε, then publishing Z preserves(ε, 2δ)-differential privacy.
Proof. First note that by the choice of t and v, using Clarkson and Woodruff [11] gives that
kSDk2F ≤ (1 ± α)kDk2F and kΨDk2F ≤ (1 ± α)kDk2F for all D with probability 1 − δ. Let A
and A′ be twoneighboring matrices such that E = A − A′ = uvT . Then kS E 0 TT k2F ≤
(1 + α)k E 0 TT k2F ≤ (1 + α)2 . Publishing Z preserves (ε, δ)-differential privacy follows from
b T and N2 and applying Theorem 37. Similarly,
considering the vector form of the matrix SAT
we use Theorem 37 and the fact that, for any matrix C of appropriate dimension, kΨCk2 ≤
b + N1 preserves differential privacy.
(1 + α)kCk2F , to prove that publishing ΨA
22

We next give a proof sketch that Yc is (ε, δ)-differentially private. This would complete the
proof of Lemma 26 as the lemma would follow by combining Lemma 35 and Theorem 36.
Claim 28. Let σmin be as in Theorem 19. Then publishing Yc preserves(ε, 2δ)-differential privacy.
Proof. Our proof uses an analysis of multivariate Gaussian distribution. 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 density function given by PDFX (x) :=
−xT Λ† x/2
√e
, where det(·) denotes the determinant of the matrix. If Λ has a non-trivial kernel
(2π)r(Σ) det(Λ)

space, then the multivariate distribution is undefined. However, in this proof, 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 ).

b −A
b ′ = ub
b = v 0m . Then A
Let A − A′ = E = uvT and let v
vT . Since ΦT is sampled
from DR , using [11], we have kΦT Wk2F = (1 + α)kWk2F for any matrix W with probability 1 − δ.
ev
eT for some unit vectors u, v
e and u
e = (1 + α)1/2 u. We
Therefore, uvT Φ = (1 + α)1/2 ue
vT = u
b
now show that AΦΩ
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 36 to prove that
the published matrix preserves (ε, δ)-differential privacy.
It may seem that the privacy of Yc follows from the result of Blocki et al. [5], but this is not
the case because of the following reasons.
1. The definition of neighboring matrices considered in this paper is different from that of Blocki
et al. [5]. To recall, Blocki et al. [5] 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 uvT for unit vectors u, v.
b and not to A as in the case
2. We multiply the Gaussian matrix to a random projection of A
b and not to A.
b
of Blocki et al. [5], i.e., to AΦ

We first give a brief overview of how to deal with these issues. The first issue is resolved by
b −A
b ′ )Φ. We observe that this expression can be represented in the form of u
ev
eT , where
analyzing (A
1/2
e = (1 + α) u for some kuk2 = 1, ke
u
vk2 = 1. The second issue can be resolved by observing that
b and AΦ
b are the same, the
Φ satisfies (α, δ)-JLP because of the choice of t. Since the rank of A
1/2
b
singular values of AΦ are within a multiplicative factor of (1 ± α)
of the singular values of Φ
with probability 1 − δ due to Sarlos [47]. Therefore, our proof goes through if we scale the singular
b appropriately.
values of A

In practical scenarios, k ≪ max {m, n} and α is a small constant. This implies that (1 − α)−1 ≈
(1 + α). If we scale the value of α appropriately, then we have the following corollary:

Corollary 29. Under the assumptions of Theorem 19 and 0 < α < 1 a small constant, given an
m×n matrix A in the turnstile update model, the algorithm Spectral-LRF, presented in Figure 1,
is (ε, δ) differentially private under Priv2 and outputs a k-rank factorization Uk , Σk , VkT (with
Mk = Uk Σk VkT , such that, with probability 9/10 over the coin tosses of Low-Space-LRF,

 √

√  p
m + n ε−1 ln(1/δ) .
k A 0 − Mk k2 ≤ (1 + α)∆k (A) + O
23

Input: A time upper bound T , privacy parameters ε, δ, and a stream s ∈ RT .

b k (τ ), Σ
b k (τ ), and V
b k (τ ).
Output: At each time step τ , output a factorization U

b
b i are initialized to
Initialization: Set t, v, Φ, S as in Figure 1. Every
Z
√ Yi and
′
′
=
δ/2 log T and ρ =
an
all
zero
matrices
for
i
∈
[log
T
].
Set
ε
=
ε/
log
T
,
δ
p
(1 + α) ln(1/δ)/ε′ .

Estimating the LRF at time t. On receiving an input (r, c, sτ ) where sτ ∈ R
at 1 ≤ τ ≤ T , form a matrix Aτ ∈ Rm×n which is an all zero matrix except with
only non-zero
P entry sτ at location (r, c) ∈ [m] × [n]. Compute i := min {j : τj 6= 0},
where τ = j τj · 2j is the binary expansion of τ . Then
b
b j and Z
b i := SAτ + P Z
b i := Aτ Φ + P Y
1. Compute Y
j<i j .
j<i
b j = 0 and Zj = Z
b j = 0. Compute Yi =
2. For j := 0, · · · , i − 1, set Yj = Y
P
2 ×n
2 m×v
b
b
Yi + N (0, ρ )
and Zi = Zi + N (0, ρ )
. Compute Y(τ ) = j:τj =1 Yj
P
and Z(τ ) = j:τj =1 Zj .

3. Compute a matrix U ∈ Rm×t whose columns are an orthonormal basis for
the column space of Y(τ ).

eΣ
eV
e T.
4. Compute the singular value decomposition of SU ∈ Rv×t . Let it be U

e T [U
eU
e T Z(τ )]k . Let it be
eΣ
e †U
5. Compute the singular value decomposition of V
′ ′ ′T
UΣV .
b k (τ ) := UU′ , Σ
b k (τ ) := Σ′ and V
b k (τ ) := V′ . Let Mk (τ ) :=
6. Output U
T
Uk (τ )Σk (τ )Vk (τ ) .

Figure 3: Differentially private Low-rank Factorization Under Continual Release (ContinualLRF)

5

A Generic Transformation for Continual Release

Our algorithms for the continual release use the binary tree mechanism [8, 21] to store the sketches
of matrix generated at various time epochs. We present the algorithm in Figure 3 for the sake of
completion. We give an intuition of the algorithm by visualizing the data-structure that stores all
the sketches in the form of a binary tree. Every leaf node τ stores the sketches of Aτ , the root note
stores the sketch of the entire matrix streamed in [0, T ], and every other node n stores the sketch
corresponding to the updates in a time range represented by the leaves of the subtree rooted at n,
b i and Z
b i stores sketches involving 2i updates to A. If a query is to compute the low-rank
i.e., Y
factorization of the matrix from a particular time range [1, τ ], we find the nodes that uniquely
cover the time range [1, τ ]. We then use the value of Y(τ ) and Z(τ ) formed using those nodes to
compute the low-rank factorization. From the binary tree construction, every time epoch appears
in exactly O(log T ) nodes (from the leaf to the root node). Moreover, every range [1, τ ] appears in
at most O(log T ) nodes of the tree (including leaves and root node). A straightforward application
of the analysis of Chan et al. [8] to the proof of Corollary 17 gives us the following result.
Theorem 30. Let m, n ∈ N and ε, δ be the input parameters. Let 0 < α < 1 be an arbitrary
constant. Let A(t) ∈ Rm×n be the matrix formed until time t. Then the algorithm Continual24

LRF, presented in Figure 3, outputs an (ε, δ)-differentially private k-rank approximation Mk (t)
under continual release and under Priv1 , such that, with probability at least 9/10 over the coin
tosses of Continual-LRF,
kA(t) − Mk (t)k2 ≤

 √

p
√  −1
(1 + α)
m
+
n
ε
log
T
log(1/δ)
∆
(A(t))
+
O
.
k
(1 − α)2

We can also convert the algorithm Low-Space-LRF to one that outputs a low-rank factorization under continual release by using less space than Continual-LRF and secure under Priv2 . We
b c )i , (Y
b r )i , and (Z)
b i as we initialize
make the following changes to Continual-LRF: (i) Initialize (Y
b r and Z
b in Figure 2 for all i ∈ [log T ], (ii) we maintain (Yc )j , (Y
cc )j , (Yr )j , (Y
cr )j , Zj , and Z
bj.
Yc , Y
Theorem 31. Let m, n ∈ N and ε, δ be the input parameters. Let k be the desired rank of the
factorization. Let 0 < α < 1 be an arbitrary constant. Let A(t) ∈ Rm×n be the matrix formed
until time t. Then there is an efficient algorithm that outputs an (ε, δ)-differentially private k-rank
approximation Mk (t) under continual release and under Priv2 , such that, with probability at least
9/10,
kA(t) − Mk (t)k2 ≤


 √
p
√  −1
(1 + α)
.
∆
(A(t))
+
O
m
+
n
ε
log
T
log(1/δ)
k
(1 − α)2

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] Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Lindenstrauss
Transform Itself Preserves Differential Privacy. In FOCS, pages 410–419, 2012.
[6] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq
framework. In Chen Li, editor, PODS, pages 128–138. ACM, 2005.
[7] 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.
[8] T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics.
ACM Transactions on Information and System Security (TISSEC), 14(3):26, 2011.
25

[9] Kamalika Chaudhuri, Anand D Sarwate, and Kaushik Sinha. Near-optimal differentially private principal components. In NIPS, pages 998–1006, 2012.
[10] Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model.
In STOC, pages 205–214, 2009.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] Petros Drineas and Michael W Mahoney. Approximating a gram matrix for improved kernelbased learning. In Learning Theory, pages 323–337. Springer, 2005.
[19] 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.
[20] 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.
[21] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy
under continual observation. In STOC, pages 715–724, 2010.
[22] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211–407, 2014.
26

[23] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and Differential Privacy.
In FOCS, pages 51–60. IEEE Computer Society, 2010.
[24] 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.
[25] 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.
[26] 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.
[27] 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.
[28] Moritz Hardt and Aaron Roth. Beating randomized response on incoherent matrices. In
STOC, pages 1255–1268, 2012.
[29] Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computation. In STOC, pages 331–340, 2013.
[30] 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.
[31] Wuxuan Jiang, Cong Xie, and Zhihua Zhang. Wishart mechanism for differentially private
principal components analysis. arXiv preprint arXiv:1511.05680, 2015.
[32] William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert
space. Contemporary mathematics, 26(189-206):1, 1984.
[33] Daniel M. Kane and Jelani Nelson. Sparser Johnson-Lindenstrauss Transforms. J. ACM,
61(1):4, 2014.
[34] Ravindran Kannan, Hadi Salmasian, and Santosh Vempala. The spectral method for general
mixture models. In Learning Theory, pages 444–457. Springer, 2005.
[35] Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In
SODA, volume 5, page 1. SIAM, 2013.
[36] Zohar Karnin and Edo Liberty. Online pca with spectral bounds. In Proceedings of the 28th
Annual Conference on Computational Learning Theory (COLT), pages 505–509, 2015.
[37] Jon M Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM
(JACM), 46(5):604–632, 1999.
[38] 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.
27

[39] Frank McSherry. Spectral partitioning of random graphs. In Foundations of Computer Science,
2001. Proceedings. 42nd IEEE Symposium on, pages 529–537. IEEE, 2001.
[40] Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in inputsparsity 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.
[41] 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.
[42] 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.
[43] Christos H Papadimitriou, Hisao Tamaki, Prabhakar Raghavan, and Santosh Vempala. Latent
semantic indexing: A probabilistic analysis. In Proceedings of the seventeenth ACM SIGACTSIGMOD-SIGART symposium on Principles of database systems, pages 159–168. ACM, 1998.
[44] Christos H Papadimitriou, Hisao Tamaki, Prabhakar Raghavan, and Santosh Vempala. Latent
semantic indexing: A probabilistic analysis. In Proceedings of the seventeenth ACM SIGACTSIGMOD-SIGART symposium on Principles of database systems, pages 159–168. ACM, 1998.
[45] Mark Rudelson and Roman Vershynin. Sampling from large matrices: An approach through
geometric functional analysis. Journal of the ACM (JACM), 54(4):21, 2007.
[46] Mark Rudelson and Roman Vershynin. Non-asymptotic theory of random matrices: extreme
singular values. arXiv preprint arXiv:1003.2990, 2010.
[47] 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.
[48] John Shawe-Taylor and Nello Cristianini. Kernel methods for pattern analysis. Cambridge
university press, 2004.
[49] Kin Cheong Sou and Anders Rantzer. On generalized matrix approximation problem in the
spectral norm. Linear Algebra and its Applications, 436(7):2331–2341, 2012.
[50] 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.
[51] Jalaj Upadhyay. Random Projections, Graph Sparsification, and Differential Privacy. In
ASIACRYPT (1), pages 276–295, 2013.
[52] Jalaj Upadhyay. Differentially private linear algebra in the streaming model. arXiv preprint
arXiv:1409.5414, 2014.
[53] Jalaj Upadhyay. Randomness efficient fast-johnson-lindenstrauss transform with applications
in differential privacy and compressed sensing. arXiv preprint arXiv:1410.2470, 2014.
28

[54] Jalaj Upadhyay. Fast and space-optimal low-rank factorization in the streaming model with
application in differential privacy. arXiv preprint arXiv:1604.01429, 2016.

A

Proof of Claim 28



b ′ = A′ σmin Im , where
b = A σmin Im and by A
We now return to the proof. Denote by A

b′ −A
b = uvT 0 . Let UC ΣC VT be the SVD of C = AΦ
b and U
e CΣ
e CV
eT
A − A′ = uvT . Then A
C
C
e =A
b ′ Φ. From above discussion, we know that if A − A′ = uvT , then C − C
e =
be the SVD of C
ev
eT for some unit vectors u
e and v
e . For notational brevity, in what follows we write u for
(1 + α)1/2 u
e and v for v
e.
u
e is a full rank matrix because of the construction; therefore CCT is
Note that both C and C
a full 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 det(CCT ) is non-zero).
e is just a linear
That is, the PDF of the distributions of the rows, corresponding to C and C,
t
transformation of N (0, Im×m ). Let y ∼ N (0, 1) .
PDFCY (x) = p

Let ε0 = √

PDFCY
e (x) = q

ε
4t ln(1/δ) log(1/δ)

1

(2π)d det(CCT )
1
eC
e T)
(2π)d det(C

1

T )−1 xT )

1

e e T )−1 xT )

e(− 2 x(CC
e(− 2 x(CC

and δ0 = δ/2t, We prove that every row of the published matrix

is (ε0 , δ0 ) differentially private; the theorem follows from Theorem 36. Let x be sampled either
eC
e T ). It is straightforward to see that the combination of Claim 32 and
from N (0, CCT ) or N (0, C
Claim 33 proves differential privacy for a row of published matrix. The lemma then follows by an
application of Theorem 36 and our choice of ε0 and δ0 .
Claim 32. Let C and ε0 be as defined above. Then
s
det(CCT )
−ε0
e
≤
≤ eε0 .
T
e
e
det(CC )

Proof. The claim
Q follows simply as in [5] after a slight modification. More concretely, we have
det(CCT ) = i σi2 , where σ1 ≥ · · · ≥ σm ≥ σmin (C) are the singular values of C. Let σ
e ≥ ··· ≥
√ 1
e
e
σ
em ≥ σmin (C) be its singular value for C. The matrix E has only one singular value 1 + α. This
is because EET = (1 + α)vvT . To finish the proof of this claim, we use Theorem 41.
e
e
Since
√ values of C − C and C − C are the same, Lidskii’s theorem (Theorem 41)
P the singular
gives i (σi − σ
ei ) ≤ 1 + α. Therefore, with probability 1 − δ,
v
!
P

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

i:e
σi ≥σi

The first inequality holds because Φ ∼ DR satisfies (α, δ)-JLP due to the choice of t. Since
C and A have same rank, this implies that all the singular values of C are within a (1 ± α)1/2
29

b due to a result by Sarlos [47]. In other words, σi ≥ σmin (C) ≥ (1 −
multiplicative factor of A
1/2
α) σ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 32.

Claim 33. Let C, ε0 , and δ0 be as defined earlier. Let y ∼ N (0, 1)m . If x is sampled either from
e then we have
Cy or Cy,
h
i
eC
e T )−1 x ≤ ε0 ≥ 1 − δ0 .
Pr xT (CCT )−1 x − xT (C

e is analogous.
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 for all 1 ≤ i, j ≤ m and COV((Ω)i,j ) = 1 if and only if
Let C − C
i = j. Then
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
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



T
e CΣ
e −2 U
e T )x
vT (U
xT (UC Σ−1
C
C VC )u
C



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

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




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




T
T e e −1 e T
U
)v
τ
=
u
(
V
τ3 = yT CT (UC Σ−2
Σ
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
kΣ
in the above expression is a linear combination of a Gaussian, i.e., each term is
per N (0, kτi k2 ), we calculate kτi k as below.
√
−1 T
1 + α,
= k(VC ΣC UT
C )(UC ΣC VC )uk2 ≤ kuk2 ≤
T e e −2 e T
T
T
e CΣ
e CV
e C − vu )k2
= kv (UC ΣC UC )(U
√
1
1+α
T e e −2 e T e e e T
T e e −2 e T
T
≤ kv (UC ΣC UC )UC ΣC UC k2 + kv (UC ΣC UC )vu k2 ≤
,
+ 2
σmin (C) σmin
(C)
1
−1
−2 T
= k(VC ΣC UT
,
C )(UC ΣC UC )vk2 ≤ kΣC k2 ≤
σmin (C)
e CΣ
e −1 U
e T )(U
e CΣ
e CV
e T − vuT )k2
= kuT (V
C
C
C
√
√
T e e −1 e T
T
T
−1
T
e CΣ
e CV
e C k2 + ku (V
e CΣ
e U
e C )vk2 ≤ 1 + α + 1 + α .
≤ ku (VC ΣC UC )(U
C
σmin (C)

Now since
every term τi
distributed as
kτ1 k2

kτ2 k2

kτ3 k2
kτ4 k2

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 because with probability
1 − δ0 ,
√

1+α
1+α
T
T −1
T e T e −1
x (CC ) x − x (C C) x ≤ 2
+ 2
ln(4/δ0 ) ≤ ε0 ,
σmin (C) σmin
(C)
30

where the second inequality follows from the choice of σmin and the fact that σmin (C) ≥ (1 −
α)1/2 σmin .
Lemma 26 follows by combining Claims 32 and 33.

B

Related Problems Studied in Previous Works

Differential privacy was introduced by Dwork et al. [20]. Since then, many algorithms for preserving
differential privacy have been proposed in the literature (see, Dwork and Roth [22]). Dwork et
al. [21] 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 [24, 30, 50] for various tasks. There are some recent works on differentially private
LRA as well. Blum et al. [6] first studied this problem in the Frobenius norm. This was improved
by Hardt and Roth [28] under the low coherence assumption. Upadhyay [52] later showed that one
can make the two-pass algorithm of Hardt and Roth [28] single-pass. differentially private LRA
has been studied in the spectral norm as well by many works [9, 35, 29, 27]. Recently, Dwork et
al. [24] gave a tighter analysis of the algorithm of Blum et al. [6] and used it to give a private online
algorithm for covariance matrices. We now define the problem studied in each of the work listed
above and draw the contrast with Problem 2.
Spectral low-rank approximation Kapralov and Talwar [35], Hardt and Roth [29], Hardt and
Price [27], and Upadhyay [52] studied low-rank approximation.
Problem 2. (Approximation with respect to the spectral norm). Given parameters α, β, τ , a private
m × n matrix A (where m ≪ n) and the target rank k, find a rank-k matrix B such that
Pr [kA − Bk2 ≤ γ∆k (A) + ζ] ≥ 1 − β.
Hardt and Price [27] and Jiang et al. [31] consider two matrices as neighboring if they differ in
exactly one entry by at most 1. Upadhyay [52] considered two matrices are neighboring if their
differ in at most one row or column of norm 1. Kapralov and Talwar [35] considered two matrices
as neighboring if the difference of their spectral norm is at most 1. The result of Kapralov and
Talwar [35] and Jiang et al. [31] is for ε-differential privacy (i.e., δ = 0).
Difference from this paper. We consider low-rank factorization with respect to the spectral
norm while Problem 2 studied only low-rank approximation. Moreover, granularity of privacy we
consider is more general than theirs.
Approximating the right singular vectors Dwork et al. [24] studied the following problem.
Problem 3. Given parameters α, β, τ and an m × n private matrix A (where m ≫ n)), compute
a rank-k matrix B such that with probability 1 − β
kAT A − Bk2 ≤

min

rank(Bk )≤k

31

kAT A − Bk k + ζ.

Dwork et al. [24] consider two matrices neighbouring if they differ by at most one row. They
further assume that the rows are normalized.
Difference from this paper. We consider low-rank factorization of both the right and the left
singular vectors while Problem 3 studied low-rank “approximation” of the right singular vectors.
Moreover, granularity of privacy we consider is more general than theirs.

C

Useful Facts

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 is
constructed recursively as follows:


Hn/2 Hn/2
and H1 := 1.
Hn =
Hn/2 −Hn/2
A randomized Walsh-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. A r × n subsampled randomized Hadamard matrix is constructed by multiplying
Π1..r from the left to a randomized Hadamard matrix, where Π1..r is the matrix formed by the first
r rows of a random permutation matrix.
Lemma 34. Let S be a v × m subsampled randomized Hadamard matrix, where v ≤ m and
N2 ∈ Rv×n . Then we have,
kS† N2 k2 = kN2 k2 .
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..v , where Π1..v 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† Nk2 = k(Π1..v WD)† Nk2 = k(WD)T Π†1..v Nk2
= kΠ†1..v Nk2 .

Using the fact that Π1..v is a full row rank matrix and Π1..v ΠT
1..v is an identity matrix, we have
†
T
T
−1
T
b
Π1..v = Π1..v (Π1..v Π1..v ) = Π1..v . The result follows.

Differential privacy. We use the following results about differential privacy in this paper.

Lemma 35. (Post-processing [19]). Let M(D) be an (ε, δ)-differential private mechanism for
a database D, and let h be any function, then any mechanism M′ := h(M(D)) is also (ε, δ)differentially private.

32

Theorem 36. (Composition [23]). Let ε0 , δ0 ∈ (0, 1), and δ′ > 0. If M1 , · · · , Mℓ are each (ε, δ)differential private mechanism, then the mechanism
M(D) := (M1 (D), · · · , Mℓ (D))
releasing the concatenation of each algorithm is (ε′ , ℓδ + 0 + δ′ )-differentially private for ε′ <
p
2ℓ ln(1/δ′ )ε0 + 2ℓε20 .

Theorem 37.p(Gaussian mechanism [19].) Let x, y ∈ Rn be any two vectors such that kx−yk2 ≤ c.
Let ρ = cε−1 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] + δ.

Properties of Gaussian distribution. We need the following property of a random Gaussian
matrices.
′

Fact 38. ([32, 47]) Let P ∈ Rm×n be a matrix of rank r and Q ∈ Rm×n be an m × n′ 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 t = O(r/α log(r/β)) such that D is an (α, β)-subspace embedding for generalized regression.
Matrix Theory. We use some basic results from matrix theory.
Theorem 39. (Weyl’s perturbation theorem) 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.
√
Fact 40. Let A be a rank-r matrix, then kAk2 ≤ kAkF ≤ rkAk2 .
We also need the following results for the privacy proof.
Theorem 41. (Lidskii Theorem). Let A, B be n × n Hermittian matrices. Then for any choice of
indices 1 ≤ i1 ≤ · · · ≤ ik ≤ n,
k
X
j=1

λij (A + B) ≤

k
X

λij (A) +

k
X

λij (B),

j=1

j=1

where {λi (A)}ni=1 are the eigen-values of A in decreasing order.
We need the following theorem in our proofs.
Lemma 42. (Sarlos [47]) Let Φ be a matrix that satisfies (α, β)-subspace embedding for I, then
(1 − α) ≤ kΦk2 ≤ (1 + α) with probability at least 1 − β.
Lemma 43. Given integer k and α, δ > 0, there is p = O(k log(1/δ)/α) such that if S is an
p × n (α, β)-subspace embedding matrix, then for n × k matrix U with orthonormal columns, with
probability at least 1 − δ, the spectral norm kUT ΦΦT U − Ik2 ≤ α.

Theorem 44. (Sou and Rantzer [49]). Let matrices O ∈ Rm×n , L ∈ Rm×p and R ∈ Rq×n be given.
Then
T
†
L† [UL UT
L OVR VR ]k R = argmin kO − LXRk2 ,
X,r(X)≤k

where L :=

T
UL ΣL VL

and R :=

T.
UR ΣR VR

33

