Talk

Weighted Low Rank Approximations
with Provable Guarantees
Ilya Razenshteyn, Zhao Song, and David P. Woodruff
MIT, UT-Austin, IBM Almaden
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
1 / 22
IMDB
.
.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
2 / 22
IMDB
.
.
.
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
2 / 22
IMDB
.
.
Rating Scale : 1, 2, · · · , 10
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
2 / 22
IMDB
.
.
Lowest Rated
Rating Scale : 1, 2, · · · , 10
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
2 / 22
IMDB
.
.
Top Rated
Lowest Rated
Rating Scale : 1, 2, · · · , 10
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
2 / 22
Motivation
.
.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
2
7
7
6
9
6
4
6
6
8
9
10
4
3
4
3
9
8
9
3
1
4
3
6
5
3
7
5
3
7
1
7
2
9
3
7
5
8
7
9
5
5
6
5
2
10
3
8
3
9
7
2
6
10
8
1
6
7
6
6
9
7
1
4
6
1
5
10
7
10
4
8
9
8
4
4
3
8
4
2
4
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
Action
Comedy
Historical
Cartoon
Magical
2
7
7
6
9
6
4
6
6
8
9
10
4
3
4
3
9
8
9
3
1
4
3
6
5
3
7
5
3
7
1
7
2
9
3
7
5
8
7
9
5
5
6
5
2
10
3
8
3
9
7
2
6
10
8
1
6
7
6
6
9
7
1
4
6
1
5
10
7
10
4
8
9
8
4
4
3
8
4
2
4
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
.
Action
2
9
4
7
5
2
7
8
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
10
3
2
6
6
1
9
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
Magical
Comedy
Historical
Cartoon
7
6
9
6
4
6
6
8
4
3
4
3
9
8
9
3
1
6
5
3
7
5
3
7
1
9
3
7
5
8
7
9
5
5
2
10
3
8
3
9
7
10
8
1
6
7
6
6
9
4
6
1
5
10
7
10
4
8
4
4
3
8
4
2
4
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
.
Comedy
Action
2
9
4
7
5
2
7
8
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
10
3
2
6
6
1
9
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
4
6
9
5
10
4
8
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
6
3
4
5
3
2
8
6
4
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
Magical
Historical
Cartoon
9
6
4
6
6
8
3
9
8
9
3
1
3
7
5
3
7
1
7
5
8
7
9
5
10
3
8
3
9
7
1
6
7
6
6
9
1
5
10
7
10
4
4
3
8
4
2
4
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
.
Comedy
Action
2
9
4
7
5
2
7
8
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
10
3
2
6
6
1
9
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
4
6
9
5
10
4
8
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
6
3
4
5
3
2
8
6
4
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
Historical
9
3
3
7
10
1
1
4
1
3
1
6
1
4
1
2
1
7
1
5
1
4
1
1
6
9
7
5
3
6
5
3
1
3
1
6
1
4
1
2
1
7
1
5
1
4
1
1
Cartoon
Magical
4
6
6
8
8
9
3
1
5
3
7
1
8
7
9
5
8
3
9
7
7
6
6
9
10
7
10
4
8
4
2
4
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
.
Comedy
Action
2
9
4
7
5
2
7
8
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
10
3
2
6
6
1
9
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
4
6
9
5
10
4
8
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
6
3
4
5
3
2
8
6
4
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
Historical
9
3
3
7
10
1
1
4
1
3
1
6
1
4
1
2
1
7
1
5
1
4
1
1
6
9
7
5
3
6
5
3
1
3
1
6
1
4
1
2
1
7
1
5
1
4
1
1
Cartoon
4
8
5
8
8
7
10
8
1
2
1
1
1
2
1
1
1
5
1
1
1
3
1
4
6
9
3
7
3
6
7
4
1
2
1
1
1
2
1
1
1
5
1
1
1
3
1
4
Magical
6
8
3
1
7
1
9
5
9
7
6
9
10
4
2
4
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Motivation
.
.
.
.
Comedy
Action
2
9
4
7
5
2
7
8
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
10
3
2
6
6
1
9
1
5
1
1
1
1
1
5
1
1
1
4
1
6
1
1
7
4
6
9
5
10
4
8
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
6
3
4
5
3
2
8
6
4
1
1
1
1
1
1
1
6
1
3
1
2
1
2
1
4
Historical
9
3
3
7
10
1
1
4
1
3
1
6
1
4
1
2
1
7
1
5
1
4
1
1
6
9
7
5
3
6
5
3
1
3
1
6
1
4
1
2
1
7
1
5
1
4
1
1
Cartoon
4
8
5
8
8
7
10
8
1
2
1
1
1
2
1
1
1
5
1
1
1
3
1
4
6
9
3
7
3
6
7
4
1
2
1
1
1
2
1
1
1
5
1
1
1
3
1
4
Magical
6
3
7
9
9
6
10
2
.
Razenshteyn-Song-Woodruff
1
2
1
2
1
6
1
4
1
2
1
3
1
6
1
2
8
1
1
5
7
9
4
4
1
2
1
2
1
6
1
4
1
2
1
3
1
6
1
2
.
Weighted Low Rank Approximations with Provable Guarantees
3 / 22
Matrix
Completion
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Matrix
Completion
.
.
n2
Given : A ∈ {R, ?} , Ω ⊂ [n] × [n] and k ∈ R
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Matrix
Completion
.
Given : A ∈ {R, ?}

1 ? ?
? 1 0
A=
? 0 1
0 ? ?
n2
, Ω ⊂ [n] × [n] and k ∈ R

0
?
, k = 2
?
1
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Matrix
Completion
.
Given : A ∈ {R, ?}

1 ? ?
? 1 0
A=
? 0 1
0 ? ?
n2
.
, Ω ⊂ [n] × [n] and k ∈ R

0
?
, k = 2
?
1
Output : AΩ̄ s.t. rank(A) = k
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Matrix
Completion
.
Given : A ∈ {R, ?}

1 ? ?
? 1 0
A=
? 0 1
0 ? ?
n2
.
, Ω ⊂ [n] × [n] and k ∈ R

0
?
, k = 2
?
1
Output : AΩ̄ s.t. rank(A) = k



1 1 0 0
1
1 1 0 0
0


A=
0 0 1 1, A = 1
0 0 1 1
0
0
1
0
1
1
0
1
0

0
1
.
0
1
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Matrix
Completion
.
Given : A ∈ {R, ?}

1 ? ?
? 1 0
A=
? 0 1
0 ? ?
n2
.
, Ω ⊂ [n] × [n] and k ∈ R

0
?
, k = 2
?
1
Output : AΩ̄ s.t. rank(A) = k
Algorithm : Candes-Recht’09, Candes-Recht’10, Keshavan’12
Hardt-Wootters’14, Jain-Netrapalli-Sanghavi’13
Hardt’15, Sun-Luo’15
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Matrix
Completion
.
Given : A ∈ {R, ?}

1 ? ?
? 1 0
A=
? 0 1
0 ? ?
n2
.
, Ω ⊂ [n] × [n] and k ∈ R

0
?
, k = 2
?
1
Output : AΩ̄ s.t. rank(A) = k
Algorithm : Candes-Recht’09, Candes-Recht’10, Keshavan’12
Hardt-Wootters’14, Jain-Netrapalli-Sanghavi’13
Hardt’15, Sun-Luo’15
Hardness : Peeters’96, Gillis-Glineur’11
Hardt-Meka-Raghavendra-Weitz’14
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Matrix
Completion
.
Given : A ∈ {R, ?}

1 ? ?
? 1 0
A=
? 0 1
0 ? ?
n2
.
, Ω ⊂ [n] × [n] and k ∈ R

0
?
, k = 2
?
1
Output : AΩ̄ s.t. rank(A) = k
Algorithm : Candes-Recht’09, Candes-Recht’10, Keshavan’12
Hardt-Wootters’14, Jain-Netrapalli-Sanghavi’13
Hardt’15, Sun-Luo’15
Hardness : Peeters’96, Gillis-Glineur’11
Hardt-Meka-Raghavendra-Weitz’14
Weighted : Srebro-Jaakkola’03, Li-Liang-Risteski’16
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
4 / 22
Weighted
Matrix Completion
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
5 / 22
Weighted
Matrix Completion
.
2
Given :A ∈ {R, ?}n , Ω ⊂ [n]2
.
2
A ∈ {R}n W ∈ {0, 1}n
.
Razenshteyn-Song-Woodruff
2
.
Weighted Low Rank Approximations with Provable Guarantees
5 / 22
Weighted
Matrix Completion
.
2
Given :A ∈ {R, ?}n , Ω ⊂ [n]2
k ∈N
.
2
A ∈ {R}n W ∈ {0, 1}n
k ∈ N, r ∈ N
.
Razenshteyn-Song-Woodruff
2
.
Weighted Low Rank Approximations with Provable Guarantees
5 / 22
Weighted
Matrix Completion
.
.
2
Given :A ∈ {R, ?}n , Ω ⊂ [n]2
k ∈N


1 ? ? 0
? 1 0 ?

A=
? 0 1 ?
0 ? ? 1
2

1
2
A=
6
0
5
1
0
5
.
Razenshteyn-Song-Woodruff
2
A ∈ {R}n W ∈ {0, 1}n
k ∈ N, r ∈ N


1 0 0
8 0
0 1 1
0 9
W =
0 1 1
1 4
1 0 0
3 1

1
0

0
1
.
Weighted Low Rank Approximations with Provable Guarantees
5 / 22
Weighted
Matrix Completion
.
.
2
Given :A ∈ {R, ?}n , Ω ⊂ [n]2
k ∈N


1 ? ? 0
? 1 0 ?

A=
? 0 1 ?
0 ? ? 1
k =2
2

1
2
A=
6
0
5
1
0
5

1
0

0
1
k = 2, r = 2
.
Razenshteyn-Song-Woodruff
2
A ∈ {R}n W ∈ {0, 1}n
k ∈ N, r ∈ N


1 0 0
8 0
0 1 1
0 9
W =
0 1 1
1 4
1 0 0
3 1
.
Weighted Low Rank Approximations with Provable Guarantees
5 / 22
Weighted
Matrix Completion
.
.
2
Given :A ∈ {R, ?}n , Ω ⊂ [n]2
k ∈N


1 ? ? 0
? 1 0 ?

A=
? 0 1 ?
0 ? ? 1
2

1
2
A=
6
0
5
1
0
5

1
0

0
1
k = 2, r = 2
k =2
Output : AΩ̄
s.t. rank(A) = k
B
s.t. rank(B) = k
kW ◦ (A − B)k2F = 0
.
Razenshteyn-Song-Woodruff
2
A ∈ {R}n W ∈ {0, 1}n
k ∈ N, r ∈ N


1 0 0
8 0
0 1 1
0 9
W =
0 1 1
1 4
1 0 0
3 1
.
Weighted Low Rank Approximations with Provable Guarantees
5 / 22
Main Results - Summary
Algorithm for Weighted low rank approximation(WLRA) problem
.
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
6 / 22
Main Results - Summary
Algorithm for Weighted low rank approximation(WLRA) problem
I
W has r distinct rows and columns
.

1
1

2
W =
2

2
7
1
1
2
2
2
7
1
1
2
2
2
7
3
3
5
5
5
4
3
3
5
5
5
4

4
4

0
, r = 3
0

0
6
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
6 / 22
Main Results - Summary
Algorithm for Weighted low rank approximation(WLRA) problem
I
I
W has r distinct rows and columns
W has r distinct columns
.

1
2

3
W =
4

5
6
1
2
3
4
5
6
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1

1
3

5
, r = 3
1

3
5
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
6 / 22
Main Results - Summary
Algorithm for Weighted low rank approximation(WLRA) problem
I
I
I
W has r distinct rows and columns
W has r distinct columns
W has rank at most r
.

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4
, r = 3
4

5
6
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
6 / 22
Main Results - Summary
Algorithm for Weighted low rank approximation(WLRA) problem
I
I
I
W has r distinct rows and columns
W has r distinct columns
W has rank at most r
Hardness for Weighted low rank approximation(WLRA) problem
.
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
6 / 22
r . Distinct Rows and Columns
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given :
2
.
2
A ∈ Rn , W ∈ Rn , r ∈ N, k ∈ N, > 0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given :
2
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given :
2
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
.
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
Output :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given :
Output :
2
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
.
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
2
rank-k B ∈ Rn s.t.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
2
.
2
Given :
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + )
2
min
rank −k A 0
kW ◦ (A − A 0 )k2F
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given. :
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + )
2
.
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
2
min
rank −k A 0
P
i,j
0 )2
W 2i,j (Ai,j − Ai,j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given. :
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
2
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given. :
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
2
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given. :
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
e 2
in O((nnz(A) + nnz(W )) · nγ ) + n · 2O(k r /) time
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
2
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given. :
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
e 2
in O((nnz(A) + nnz(W )) · nγ ) + n · 2O(k r /) time
for an arbitrarily small constant γ > 0
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
2
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Rows and Columns
Given. :
A ∈ Rn , W

1 1
1 1

2 2
W =
2 2

2 2
7 7
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
e 2
in O((nnz(A) + nnz(W )) · nγ ) + n · 2O(k r /) time
for an arbitrarily small constant γ > 0
fixed parameter tractable
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 3 3 4
1 3 3 4

2 5 5 0
, r = 3
2 5 5 0

2 5 5 0
7 4 4 6
2
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
7 / 22
r . Distinct Columns
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
Given :
2
.
2
A ∈ Rn , W ∈ Rn , r ∈ N, k ∈ N, > 0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
Given :
2
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
.
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
Given :
2
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
.
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
Output :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
Given :
Output :
2
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
.
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
2
rank-k B ∈ Rn s.t.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
2
.
2
Given :
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + )
2
min
rank −k A 0
kW ◦ (A − A 0 )k2F
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
.
Given. :
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + )
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
2
min
rank −k A 0
P
i,j
0 )2
W 2i,j (Ai,j − Ai,j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
.
Given. :
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
.
Given. :
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
.
Given. :
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
e 2 2
in O((nnz(A) + nnz(W )) · nγ ) + n · 2O(k r /) time
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
.
Given. :
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
e 2 2
in O((nnz(A) + nnz(W )) · nγ ) + n · 2O(k r /) time
for an arbitrarily small constant γ > 0
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
r . Distinct Columns
.
Given. :
A ∈ Rn , W

1 1
2 2

3 3
W =
4 4

5 5
6 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
e 2 2
in O((nnz(A) + nnz(W )) · nγ ) + n · 2O(k r /) time
for an arbitrarily small constant γ > 0
fixed parameter tractable
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 1 1 1
2 1 1 3

3 1 1 5
, r = 3
4 1 1 1

5 1 1 3
6 1 1 5
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
8 / 22
Rank
r
.
.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
Given :
.
2
2
A ∈ Rn , W ∈ Rn , r ∈ N, k ∈ N, > 0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
Given :
.
2
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
Given :
.
2
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
Output :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
Given :
Output :
.
2
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
2
rank-k B ∈ Rn s.t.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
.
2
2
Given :
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + )
2
min
rank −k A 0
kW ◦ (A − A 0 )k2F
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
.
Given. :
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + )
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
2
min
rank −k A 0
P
i,j
0 )2
W 2i,j (Ai,j − Ai,j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
.
Given. :
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
.
Given. :
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
.
Given. :
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
2
in nO(k
2 r /)
time
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Rank
r
.
.
Given. :
A ∈ Rn , W

1 1
0 1

1 1
W =
0 0

1 0
0 0
Output :
rank-k B ∈ Rn s.t.
kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
2
2
∈ Rn , r ∈ N, k ∈ N, > 0

1 2 2 2
2 1 2 3

3 2 4 4
, r = 3
4 0 4 4

5 1 6 5
6 0 6 6
2
2
in nO(k r /) time
previously only r =1 was known to be in polynomial time
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
9 / 22
Main
Results - Hardness
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
.
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
Given : random 4-SAT formula S on n variables
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
Given : random 4-SAT formula S on n variables
each clause has 4 literals
S1
(x4 ∨ x32 ∨ x9 ∨ x20 )
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
Given : random 4-SAT formula S on n variables
each clause has 4 literals
each of Θ(n4 ) clauses is picked ind. with prob. Θ(1/n3 )
S1
S2
SΘ(n)
.
Razenshteyn-Song-Woodruff
(x4 ∨ x32 ∨ x9 ∨ x20 )
(x2 ∨ x13 ∨ x5 ∨ x25 )
······
(x11 ∨ x19 ∨ x24 ∨ x6 )
S = S1 ∧ S2 ∧ · · · ∧ SΘ(n)
Weighted Low Rank Approximations with Provable Guarantees
.
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
Given : random 4-SAT formula S on n variables
each clause has 4 literals
each of Θ(n4 ) clauses is picked ind. with prob. Θ(1/n3 )
Any algorithm that
S1
S2
SΘ(n)
.
Razenshteyn-Song-Woodruff
(x4 ∨ x32 ∨ x9 ∨ x20 )
(x2 ∨ x13 ∨ x5 ∨ x25 )
······
(x11 ∨ x19 ∨ x24 ∨ x6 )
S = S1 ∧ S2 ∧ · · · ∧ SΘ(n)
Weighted Low Rank Approximations with Provable Guarantees
.
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
Given : random 4-SAT formula S on n variables
each clause has 4 literals
each of Θ(n4 ) clauses is picked ind. with prob. Θ(1/n3 )
Any algorithm that
outputs 1 with prob. 1 when S is satisfiable
S1
S2
SΘ(n)
.
Razenshteyn-Song-Woodruff
(x4 ∨ x32 ∨ x9 ∨ x20 )
(x2 ∨ x13 ∨ x5 ∨ x25 )
······
(x11 ∨ x19 ∨ x24 ∨ x6 )
S = S1 ∧ S2 ∧ · · · ∧ SΘ(n)
Weighted Low Rank Approximations with Provable Guarantees
.
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
Given : random 4-SAT formula S on n variables
each clause has 4 literals
each of Θ(n4 ) clauses is picked ind. with prob. Θ(1/n3 )
Any algorithm that
outputs 1 with prob. 1 when S is satisfiable
outputs 0 with prob. > 1/2 when S is unsatisfiable
S1
S2
SΘ(n)
.
Razenshteyn-Song-Woodruff
(x4 ∨ x32 ∨ x9 ∨ x20 )
(x2 ∨ x13 ∨ x5 ∨ x25 )
······
(x11 ∨ x19 ∨ x24 ∨ x6 )
S = S1 ∧ S2 ∧ · · · ∧ SΘ(n)
Weighted Low Rank Approximations with Provable Guarantees
.
10 / 22
Main Results - Hardness
. [Feige’02, Goerdt-Lanka’04]
.
Random-4SAT Hypothesis
Given : random 4-SAT formula S on n variables
each clause has 4 literals
each of Θ(n4 ) clauses is picked ind. with prob. Θ(1/n3 )
Any algorithm that
outputs 1 with prob. 1 when S is satisfiable
outputs 0 with prob. > 1/2 when S is unsatisfiable
Requires :
2Ω(n) time
S1
S2
SΘ(n)
.
Razenshteyn-Song-Woodruff
(x4 ∨ x32 ∨ x9 ∨ x20 )
(x2 ∨ x13 ∨ x5 ∨ x25 )
······
(x11 ∨ x19 ∨ x24 ∨ x6 )
S = S1 ∧ S2 ∧ · · · ∧ SΘ(n)
Weighted Low Rank Approximations with Provable Guarantees
.
10 / 22
Main
Results - Hardness
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Main
Results - Hardness
.
.
Weighted Low Rank Approximation Hardness
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Main
Results - Hardness
.
.
Weighted Low Rank Approximation Hardness
Given :
2
A ∈ Rn , distinct r columns W ∈ Rn
2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Main
Results - Hardness
.
.
Weighted Low Rank Approximation Hardness
Given :
2
2
A ∈ Rn , distinct r columns W ∈ Rn
k ∈ N, > 0, W ij ∈ {0, 1, 2, · · · , poly(n)}
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Main
Results - Hardness
.
.
Weighted Low Rank Approximation Hardness
2
2
Given :
A ∈ Rn , distinct r columns W ∈ Rn
k ∈ N, > 0, W ij ∈ {0, 1, 2, · · · , poly(n)}
Output :
rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Main
Results - Hardness
.
.
Weighted Low Rank Approximation Hardness
2
2
Given :
A ∈ Rn , distinct r columns W ∈ Rn
k ∈ N, > 0, W ij ∈ {0, 1, 2, · · · , poly(n)}
Output :
rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
Assume :
Random-4SAT
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Main
Results - Hardness
.
.
Weighted Low Rank Approximation Hardness
2
2
Given :
A ∈ Rn , distinct r columns W ∈ Rn
k ∈ N, > 0, W ij ∈ {0, 1, 2, · · · , poly(n)}
Output :
rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
Assume :
Random-4SAT
∃0 > 0, for any algorithm with < 0 and k > 1
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Main
Results - Hardness
.
.
Weighted Low Rank Approximation Hardness
2
2
Given :
A ∈ Rn , distinct r columns W ∈ Rn
k ∈ N, > 0, W ij ∈ {0, 1, 2, · · · , poly(n)}
Output :
rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
with prob. 9/10
Assume :
Random-4SAT
Requires :
∃0 > 0, for any algorithm with < 0 and k > 1
2Ω(r ) time !
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
11 / 22
Outline of Technique
Obtain a lower bound on the cost
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
12 / 22
Outline of Technique
Obtain a lower bound on the cost
Polynomial system verifier
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
12 / 22
Outline of Technique
Obtain a lower bound on the cost
Polynomial system verifier
Multiple regression sketch
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
12 / 22
Outline of Technique
Obtain a lower bound on the cost
Polynomial system verifier
Multiple regression sketch
Inefficient WLRA algorithm
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
12 / 22
Outline of Technique
Obtain a lower bound on the cost
Polynomial system verifier
Multiple regression sketch
Inefficient WLRA algorithm
Guess a sketch
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
12 / 22
Lower
Bound on the Cost
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
Given: a real polynomial system P(x)
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
where ∆i ∈ {=, >}
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
where ∆i ∈ {=, >}
d : maximum degree over all polynomials
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
where ∆i ∈ {=, >}
d : maximum degree over all polynomials
H : the maximum absolute value of the coefficients
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
. a real polynomial system P(x)
Given:
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
where ∆i ∈ {=, >}
d : maximum degree over all polynomials
H : the maximum absolute value of the coefficients
Rv
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
. a real polynomial system P(x)
Given:
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
where ∆i ∈ {=, >}
d : maximum degree over all polynomials
H : the maximum absolute value of the coefficients
T : {x ∈ Rv |f1 (x) > 0, · · · , f` (x) > 0, f`+1 (x) = 0, · · · , fm (x) = 0}
Rv
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
. a real polynomial system P(x)
Given:
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
where ∆i ∈ {=, >}
d : maximum degree over all polynomials
H : the maximum absolute value of the coefficients
T : {x ∈ Rv |f1 (x) > 0, · · · , f` (x) > 0, f`+1 (x) = 0, · · · , fm (x) = 0}
minimum value that nonnegative g takes over T is either 0 or > (H + m)−d
v
Rv
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Lower Bound on the Cost
.
[Jeronimo-Perrucci-Tsigaridas’13]
. a real polynomial system P(x)
Given:
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomials constraints fi ∆i (x) > 0, ∀i ∈ [m]
where ∆i ∈ {=, >}
d : maximum degree over all polynomials
H : the maximum absolute value of the coefficients
T : {x ∈ Rv |f1 (x) > 0, · · · , f` (x) > 0, f`+1 (x) = 0, · · · , fm (x) = 0}
v
min nonzero cost > (H + m)−d
Rv
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
13 / 22
Polynomial
System Verifier
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
Given: a real polynomial system P(x)
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomial constraints fi (x)∆i 0, ∀i ∈ [m]
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomial constraints fi (x)∆i 0, ∀i ∈ [m]
where ∆i ∈ {>, >, =, 6=, <, 6}
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomial constraints fi (x)∆i 0, ∀i ∈ [m]
where ∆i ∈ {>, >, =, 6=, <, 6}
d : maximum degree over all polynomial constraints
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomial constraints fi (x)∆i 0, ∀i ∈ [m]
where ∆i ∈ {>, >, =, 6=, <, 6}
d : maximum degree over all polynomial constraints
H : the maximum absolute value of the coefficients
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Polynomial System Verifier
. Basu-Pollack-Roy’96]
[Renegar’92,
Given: a real polynomial system P(x)
v : #variables, x = (x1 , x2 , · · · , xv )
m : #polynomial constraints fi (x)∆i 0, ∀i ∈ [m]
where ∆i ∈ {>, >, =, 6=, <, 6}
d : maximum degree over all polynomial constraints
H : the maximum absolute value of the coefficients
It takes (md)O(v ) poly(log H) time to
decide if ∃ a solution to polynomial system P
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
14 / 22
Multiple
Regression Sketch
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
Given :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
Given :
A(1) , A(2) , · · · , A(m) ∈ Rn×k
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
Given :
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
Denote x (j) = arg minkA(j) x − b(j) k, ∀j ∈ [m]
Given :
x∈Rk×1
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
Denote x (j) = arg minkA(j) x − b(j) k, ∀j ∈ [m]
Given :
x∈Rk×1
Choose :
S to be a random Gaussian matrix
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
Denote x (j) = arg minkA(j) x − b(j) k, ∀j ∈ [m]
Given :
x∈Rk×1
Choose : S to be a random Gaussian matrix
Denote y (j) = arg minkSA(j) y − Sb(j) k, ∀j ∈ [m]
y∈Rk ×1
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
Denote x (j) = arg minkA(j) x − b(j) k, ∀j ∈ [m]
Given :
x∈Rk×1
Choose : S to be a random Gaussian matrix
Denote y (j) = arg minkSA(j) y − Sb(j) k, ∀j ∈ [m]
y∈Rk ×1
Gaurantee :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
Denote x (j) = arg minkA(j) x − b(j) k, ∀j ∈ [m]
Given :
x∈Rk×1
Choose : S to be a random Gaussian matrix
Denote y (j) = arg minkSA(j) y − Sb(j) k, ∀j ∈ [m]
y∈Rk ×1
Gaurantee : For all ∈ (0, 1/2), one can set t = O(k/) s.t.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
Denote x (j) = arg minkA(j) x − b(j) k, ∀j ∈ [m]
Given :
x∈Rk×1
Choose : S to be a random Gaussian matrix
Denote y (j) = arg minkSA(j) y − Sb(j) k, ∀j ∈ [m]
y∈Rk ×1
Gaurantee : For all ∈ (0, 1/2), one can set t = O(k/) s.t.
m
m
P
P
kA(j) y (j) − b(j) k22 6 (1 + ) kA(j) x (j) − b(j) k22
j=1
j=1
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Multiple
Regression Sketch
.
.
A(1) , A(2) , · · · , A(m) ∈ Rn×k
b(1) , b(2) , · · · , b(m) ∈ Rn×1
Denote x (j) = arg minkA(j) x − b(j) k, ∀j ∈ [m]
Given :
x∈Rk×1
Choose : S to be a random Gaussian matrix
Denote y (j) = arg minkSA(j) y − Sb(j) k, ∀j ∈ [m]
y∈Rk ×1
Gaurantee : For all ∈ (0, 1/2), one can set t = O(k/) s.t.
m
m
P
P
kA(j) y (j) − b(j) k22 6 (1 + ) kA(j) x (j) − b(j) k22
j=1
j=1
with prob. 9/10
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
15 / 22
Inefficient
WLRA Algorithm
.
.
Razenshteyn-Song-Woodruff
.
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Aij ∈ {0, ±1, ±2, · · · , ±∆}
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
W ij ∈ {0, 1, 2, · · · , ∆}
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2. write polynomial g(x1 , · · · , x2nk ) = kW ◦ (A − UV )k2F
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2. write polynomial g(x1 , · · · , x2nk ) = kW ◦ (A − UV )k2F
3. pick C ∈ [L− , L+ ], run polynomial verifier g(x) 6 C
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2. write polynomial g(x1 , · · · , x2nk ) = kW ◦ (A − UV )k2F
3. pick C ∈ [L− , L+ ], run polynomial verifier g(x) 6 C
4. optimize C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2. write polynomial g(x1 , · · · , x2nk ) = kW ◦ (A − UV )k2F
3. pick C ∈ [L− , L+ ], run polynomial verifier g(x) 6 C
4. optimize C by binary search over [L− , L+ ]
Time :
2Ω(nk)
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2. write polynomial g(x1 , · · · , x2nk ) = kW ◦ (A − UV )k2F
3. pick C ∈ [L− , L+ ], run polynomial verifier g(x) 6 C
4. optimize C by binary search over [L− , L+ ]
Time :
2Ω(nk)
How can we do better?
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
Time :
2Ω(nk)
How can we do better?
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2Ω(nk)
How can we do better?
polynomial verifier runs in (# constraints · degree)O(# variables)
Time :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2Ω(nk)
How can we do better?
polynomial verifier runs in (# constraints · degree)O(# variables)
O(# variables)
lower bound on cost
(# constraints)−degree
Time :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2Ω(nk)
How can we do better?
polynomial verifier runs in (# constraints · degree)O(# variables)
O(# variables)
lower bound on cost
(# constraints)−degree
write a polynomial with few #variables, i.e. poly(kr )
Time :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Inefficient
WLRA Algorithm
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Output : rank-k B s.t. kW ◦ (A − B)k2F 6 (1 + ) OPT
Algorithm :
1. create variables 2nk variables for U, V > ∈ Rn×k
2Ω(nk)
How can we do better?
polynomial verifier runs in (# constraints · degree)O(# variables)
O(# variables)
lower bound on cost
(# constraints)−degree
write a polynomial with few #variables, i.e. poly(kr )
without blowing up degree and #constraints too much
Time :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
16 / 22
Guess
a Sketch
.
.
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Aij ∈ {0, ±1, ±2, · · · , ±∆}
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
W ij ∈ {0, 1, 2, · · · , ∆}
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be jth column of W
DW j be diagonal matrix with vector W j


1 1 1 2 2 2
0 1 2 1 2 3


1 1 3 2 4 4

W =
0 0 4 0 4 4


1 0 5 1 6 5
0 0 6 0 6 6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be jth column of W
DW j be diagonal matrix with vector W j




1 1 1 2 2 2
1
0 1 2 1 2 3
 0





1 1 3 2 4 4


1



W =
0 0 4 0 4 4 DW 1 = 

0




1 0 5 1 6 5

1 
0 0 6 0 6 6
0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be jth column of W
DW j be diagonal matrix with vector W j




1 1 1 2 2 2
1
0 1 2 1 2 3
 1





1 1 3 2 4 4


1



W =
0 0 4 0 4 4 DW 2 = 

0




1 0 5 1 6 5

0 
0 0 6 0 6 6
0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be jth column of W
DW j be diagonal matrix with vector W j




1 1 1 2 2 2
1
0 1 2 1 2 3
 2





1 1 3 2 4 4


3



W =
0 0 4 0 4 4 DW 3 = 

4




1 0 5 1 6 5

5 
0 0 6 0 6 6
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be jth column of W
DW j be diagonal matrix with vector W j




1 1 1 2 2 2
2
0 1 2 1 2 3
 1





1 1 3 2 4 4


2



W =
0 0 4 0 4 4 DW 4 = 

0




1 0 5 1 6 5

1 
0 0 6 0 6 6
0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be jth column of W
DW j be diagonal matrix with vector W j




1 1 1 2 2 2
2
0 1 2 1 2 3
 2





1 1 3 2 4 4


4



W =
0 0 4 0 4 4 DW 5 = 

4




1 0 5 1 6 5

6 
0 0 6 0 6 6
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be jth column of W
DW j be diagonal matrix with vector W j




1 1 1 2 2 2
2
0 1 2 1 2 3
 3





1 1 3 2 4 4


4



W =
0 0 4 0 4 4 DW 6 = 

4




1 0 5 1 6 5

5 
0 0 6 0 6 6
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
k(UV − A) ◦ W k2F
Algorithm :

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
= k(UV − A) ◦ W k2F
Algorithm :
2
V
( U
−
A
)◦
F
.
Razenshteyn-Song-Woodruff
W
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
= k(UV − A) ◦ W k2F
2
j=1 kDW j UV j − DW j Aj k2
Algorithm :
Pn
2
V
( U
−
A
)◦
F
.
Razenshteyn-Song-Woodruff
W
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
= k(UV − A) ◦ W k2F =
2
j=1 kDW j UV j − DW j Aj k2
Algorithm :
Pn
2
V
( U
−
A
)◦
F
.
Razenshteyn-Song-Woodruff
W
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Algorithm :
Pn
2
V
( U
−
A
)◦
F
.
Razenshteyn-Song-Woodruff
W
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Algorithm :
Pn
S
T
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
2
j=1 kSDW j UV j − SDW j Aj k2
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t


1
SDW 1 U =
S
 0





1

 U


0



1 
0
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t


1
SDW 2 U =
S
 1





1

 U


0



0 
0
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t


1
SDW 3 U =
S
 2





3

 U


4



5 
6
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t


2
SDW 4 U =
S
 1





2

 U


0



1 
0
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t


2
SDW 5 U =
S
 2





4

 U


4



6 
6
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t


2
SDW 6 U =
S
 3





4

 U


4



5 
6
Algorithm :
Pn
.
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
.
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t
Algorithm :
Pn
Create t × k variables for each of n SDW j U s?
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
.
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t
Algorithm :
Pn
Create t × k variables for each of n SDW j U s?
n ×t × k
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
.
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t
Algorithm :
Pn
Create t × k variables for each of n SDW j U s?
? ×t × k
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k /)
.
= k(UV − A) ◦ W k2F =
Pn
2
i
i
2
j=1 kDW j UV j − DW j Aj k2
i=1 kU V DW i − A DW i k2
Sketch by Gaussian S, T > ∈ Rt×n
Pn
Pn
2
i
i
2
j=1 kSDW j UV j − SDW j Aj k2
i=1 kU V DW i T − A DW i T k2
Guess SDW j U ∈ Rt×k and V DW i T ∈ Rk×t
Algorithm :
Pn
Create t × k variables for each of n SDW j U s?
r ×t × k
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
17 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6

1
0

1

0

1
0
1
1
1
0
0
0

1
2

3

4

5
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
W1 = W1
   
1
1
0 0
   
1 1
 = 
0 0
   
1 1
0
0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
W2 = W2
   
1
1
1 1
   
1 1
 = 
0 0
   
0 0
0
0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
W3 = W3
   
1
1
2 2
   
3 3
 = 
4 4
   
5 5
6
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
W4 = W1 + W2
     
2
1
1
1 0 1
     
2 1 1
 = + 
0 0 0
     
1 1 0
0
0
0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
W5 = W1 + W3
     
2
1
1
2 0 2
     
4 1 3
 = + 
4 0 4
     
6 1 5
6
0
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm : W j be ith column of W

1
0

1
W =
0

1
0
1
1
1
0
0
0
1
2
3
4
5
6
2
1
2
0
1
0
2
2
4
4
6
6

2
3

4

4

5
6
W6 = W2 + W3
     
2
1
1
3 1 2
     
4 1 3
 = + 
4 0 4
     
5 0 5
6
0
6
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
create t × k variables for SDW 1 U


1
 0





1




0



1 
0
Weighted Low Rank Approximations with Provable Guarantees
U
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
create t × k variables for SDW 2 U


1
 1





1




0



0 
0
Weighted Low Rank Approximations with Provable Guarantees
U
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
create t × k variables for SDW 3 U


1
 2





3




4



5 
6
Weighted Low Rank Approximations with Provable Guarantees
U
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 4 U as SDW 1 U + SDW 2 U


2
 1





2




0



1 
0
Weighted Low Rank Approximations with Provable Guarantees
U
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 4 U as SDW 1 U + SDW 2 U

1+1

0+1


1+1


0+0


1+0



 U



0+0
.
Razenshteyn-Song-Woodruff

Weighted Low Rank Approximations with Provable Guarantees
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 4 U as SDW 1 U + SDW 2 U

 

1
1
 0
  1


 


 

1
1



) U
(
+


0
0

 




1
0 
0
0
Weighted Low Rank Approximations with Provable Guarantees
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 5 U as SDW 1 U + SDW 3 U


2
 2





4




4



6 
6
Weighted Low Rank Approximations with Provable Guarantees
U
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 5 U as SDW 1 U + SDW 3 U

1+1

0+2


1+3


0+4


1+5



 U



0+6
.
Razenshteyn-Song-Woodruff

Weighted Low Rank Approximations with Provable Guarantees
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 5 U as SDW 1 U + SDW 3 U

 

1
1
 0
  2


 


 

1
3



) U
(
+


0
4

 




1
5 
0
6
Weighted Low Rank Approximations with Provable Guarantees
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 6 U as SDW 2 U + SDW 3 U


2
 3





4




4



5 
6
Weighted Low Rank Approximations with Provable Guarantees
U
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 6 U as SDW 2 U + SDW 3 U

1+1

1+2


1+3


0+4


0+5



 U



0+6
.
Razenshteyn-Song-Woodruff

Weighted Low Rank Approximations with Provable Guarantees
.
18 / 22
Guess
a Sketch
.
n2
Given :
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption :
.
Algorithm :
S
.
Razenshteyn-Song-Woodruff
P
k(UV − A) ◦ W k2F = nj=1 kDW j UV j − DW j Aj k22
P
sketch nj=1 kSDW j UV j − SDW j Aj k22
create variables for SDW j U, ∀i ∈ [r ]
write SDW 6 U as SDW 2 U + SDW 3 U

 

1
1
 1
  2


 


 

1
3



) U
(
+


0
4

 




0
5 
0
6
Weighted Low Rank Approximations with Provable Guarantees
.
18 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),
Algorithm :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (SDW U)† SDW Aj
write V
j
j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),
Algorithm :
SDW j U ∈ Rt×k is non-degenerate
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (SDW U)† SDW Aj
write V
j
j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),
Algorithm :
SDW j U ∈ Rt×k is non-degenerate
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = ((SDW U)> (SDW U))−1 (SDW U)> SDW Aj
write V
j
j
j
j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = ((SDW U)> (SDW U))−1 (SDW U)> SDW Aj
write V
j
j
j
j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
j =1
b1 =
V
-1
(Q >
1 Q1 )
Q>
1

S








1
0
1
0
1
0
.
Razenshteyn-Song-Woodruff



 A1



Weighted Low Rank Approximations with Provable Guarantees
.
19 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
j =2
b2 =
V
-1
(Q >
2 Q2 )
Q>
2

S








1
1
1
0
0
0
.
Razenshteyn-Song-Woodruff



 A2



Weighted Low Rank Approximations with Provable Guarantees
.
19 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
j =3
b3 =
V
-1
(Q >
3 Q3 )
Q>
3

S








1
2
3
4
5
6
.
Razenshteyn-Song-Woodruff



 A3



Weighted Low Rank Approximations with Provable Guarantees
.
19 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
j =4
b4 =
V
-1
(Q >
4 Q4 )
Q>
4

S








2
1
2
0
1
0
.
Razenshteyn-Song-Woodruff



 A4



Weighted Low Rank Approximations with Provable Guarantees
.
19 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
j =5
b5 =
V
-1
(Q >
5 Q5 )
Q>
5

S








2
2
4
4
6
6
.
Razenshteyn-Song-Woodruff



 A5



Weighted Low Rank Approximations with Provable Guarantees
.
19 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
j =6
b6 =
V
-1
(Q >
6 Q6 )
Q>
6

S








2
3
4
4
5
6
.
Razenshteyn-Song-Woodruff



 A6



Weighted Low Rank Approximations with Provable Guarantees
.
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
by Cramer’s rule
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
by Cramer’s rule

-1
(Q >
j Qj )
f11 (x) f12 (x) · · ·

1 f21 (x) f22 (x) · · ·
= hj (x)
 ···
···
···
fk1 (x) fk2 (x) · · ·

f1k (x)
f2k (x)


fkk (x)
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
Pn
2
b := arg min
V
V ∈Rk ×n
j=1 kSDW j UV j − SDW j Aj k2
b j = (Q > Q j )−1 Q > SDW Aj
write V
j
j
j
by Cramer’s rule

-1
(Q >
j Qj )
f11 (x) f12 (x) · · ·

1 f21 (x) f22 (x) · · ·
= hj (x)
 ···
···
···
fk1 (x) fk2 (x) · · ·

f1k (x)
f2k (x)


fkk (x)
polynomials h, f have degree O(k)
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
19 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
−1 gives h (x),
∀j ∈ [n], (Q >
j
j Qj )
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b
V
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b
V
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
b
V
b
U
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
degree of pji (x), gj (x), qij (x), hj (x) = O(k)
b
V
b
U
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
degree of pji (x), gj (x), qij (x), hj (x) = O(k)
Choose :
C ∈ [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
degree of pji (x), gj (x), qij (x), hj (x) = O(k)
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C
k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
degree of pji (x), gj (x), qij (x), hj (x) = O(k)
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C
k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize :
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
degree of pji (x), gj (x), qij (x), hj (x) = O(k)
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C
k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
degree of pji (x), gj (x), qij (x), hj (x) = O(k)
Not done yet.
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C
k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
−1 gives h (x),
b ij = qij (x)/hj (x)
∀j ∈ [n], (Q >
then ∀i ∈ [k ], V
j
j Qj )
b ji = pji (x)/gj (x)
∀j ∈ [n], (P j P j > )−1 gives gj (x), then ∀i ∈ [k], U
degree of pji (x), gj (x), qij (x), hj (x) = O(k)
We need to remove denominators.
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C
k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
We need to remove denominators.
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C
k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C ·G(x)
G(x)· k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
O(# variables)
(# constraints · degree)
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C ·G(x)
G(x)· k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
(
O(n)
· degree) O(# variables)
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C ·G(x)
G(x)· k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
(
O(n)
· O(nk ) ) O(# variables)
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C ·G(x)
G(x)· k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
(
O(n)
· O(nk ) ) O(krt)
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C ·G(x)
G(x)· k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
.
n2
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
(
O(n)
2
· O(nk ) ) O(rk /)
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C ·G(x)
G(x)· k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Guess
a Sketch
.
Given :
n2
.
n2
A ∈ R , W ∈ R , r ∈ N, k ∈ N, > 0
Assumption : t = O(k/),Q j =SDW j U ∈ Rt×k is non-degenerate
P j = V DW j T ∈ Rk×t is non-degenerate
Algorithm :
2
Time (n)O(rk /)
G(x) = Πnj=1 gj2 (x)hj2 (x) of degree O(nk )
Denote :
C ∈ [L− , L+ ]
Choose :
Polynomial system :
bV
b − A) ◦ W k2 6 C ·G(x)
G(x)· k(U
F
∀j ∈ [n], gj2 (x) 6= 0, hj2 (x) 6= 0
Optimize : C by binary search over [L− , L+ ]
.
Razenshteyn-Song-Woodruff
.
Weighted Low Rank Approximations with Provable Guarantees
20 / 22
Applications
Guess a sketch with coding schemes
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
21 / 22
Applications
Guess a sketch with coding schemes
I
Adversial matrix completion
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
21 / 22
Applications
Guess a sketch with coding schemes
I
Adversial matrix completion
Guess a sketch with [Landsberg-Manivel’04, Landsberg’12]
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
21 / 22
Applications
Guess a sketch with coding schemes
I
Adversial matrix completion
Guess a sketch with [Landsberg-Manivel’04, Landsberg’12]
I
Weighted low (border) rank tensor completion
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
21 / 22
Applications
Guess a sketch with coding schemes
I
Adversial matrix completion
Guess a sketch with [Landsberg-Manivel’04, Landsberg’12]
I
Weighted low (border) rank tensor completion
Guess a sketch with [Arora-Ge-Kannan-Moitra’12, Moitra’13]
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
21 / 22
Applications
Guess a sketch with coding schemes
I
Adversial matrix completion
Guess a sketch with [Landsberg-Manivel’04, Landsberg’12]
I
Weighted low (border) rank tensor completion
Guess a sketch with [Arora-Ge-Kannan-Moitra’12, Moitra’13]
I
Weighted nonnegative matrix factorization
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
21 / 22
Open Problems
Can we come up a poly(n) · 2poly(kr /) time algorithm for WLRA
problem with rank-r W or prove a nΩ(r ) lower bound for WLRA
problem with rank-r W ?
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
22 / 22
Open Problems
Can we come up a poly(n) · 2poly(kr /) time algorithm for WLRA
problem with rank-r W or prove a nΩ(r ) lower bound for WLRA
problem with rank-r W ?
Can we prove a hardness result respect to parameter k or ,
2Ω(k) or 2Ω(1/) lower bound for WLRA problem?
Razenshteyn-Song-Woodruff
Weighted Low Rank Approximations with Provable Guarantees
22 / 22