Fast greedy algorithms for dictionary selection
with generalized sparsity constraints
Kaito Fujii & Tasuku Soma

(UTokyo)

Neural Information Processing Systems 2018, spotlight presentation
Dec. 7, 2018

1/ 9

Dictionary
If real-world signals consist of a few patterns,

a “good” dictionary gives sparse representations of each signal

2/ 9

Dictionary
If real-world signals consist of a few patterns,

a “good” dictionary gives sparse representations of each signal
patch

2/ 9

Dictionary
If real-world signals consist of a few patterns,

a “good” dictionary gives sparse representations of each signal
patch

dictionary

2/ 9Dictionary
If real-world signals consist of a few patterns,

a “good” dictionary gives sparse representations of each signal
patch

sparse representation≈ 0.4+ 0.1+ 0.9≈ 0.2+ 0.2+ 0.3≈ 0.5+ 0.5+ 0.1

dictionary

2/ 9Dictionary selection [Krause–Cevher’10]
Union of existing dictionaries

DCT basis

Haar basis

Db4 basis

Coiﬂet basis

Selected atoms as a dictionary

Atoms for each patch yt (∀t ∈ [T])3/ 9

Dictionary selection [Krause–Cevher’10]
Union of existing dictionaries

DCT basis

Haar basis

Db4 basis

Coiﬂet basis

Selected atoms as a dictionary

Atoms for each patch yt (∀t ∈ [T])3/ 9

Dictionary selection [Krause–Cevher’10]
Union of existing dictionaries

DCT basis

Haar basis

Db4 basis

Coiﬂet basis

Selected atoms as a dictionary

Atoms for each patch yt (∀t ∈ [T])
≈ w1+w2+w3≈ w1+w2+w3

3/ 9

Dictionary selection [Krause–Cevher’10]
Union of existing dictionaries

DCT basis

Haar basis

Selected atoms as a dictionaryAtoms for each patch yt (∀t ∈ [T])
≈ w1+w2Z1 +w3

Db4 basis

Coiﬂet basis

X≈ w1+w2Z2 +w3

3/ 9

Dictionary selection with sparsity constraints
Maximize
X⊆Vmax(Z1 ,··· ,ZT )∈I : Zt ⊆XT∑
t=1ft (Zt )subject to |X| ≤ k

1st maximization:

selecting a set X of atoms
as a dictionary

4/ 9

Dictionary selection with sparsity constraints
Maximize
X⊆Vmax(Z1 ,··· ,ZT )∈I : Zt ⊆X

T∑
t=1ft (Zt )subject to |X| ≤ k

2nd maximization:

selecting a set Zt ⊆ X of atoms

for a sparse representation of each patch

under sparsity constraint I

4/ 9

Dictionary selection with sparsity constraints
Maximize
X⊆Vmax(Z1 ,··· ,ZT )∈I : Zt ⊆X

T∑
t=1ft (Zt )sparsity constraint

subject to |X| ≤ k
set function representing

the quality of Zt for patch yt

4/ 9

Dictionary selection with sparsity constraints
MaximizeX⊆Vmax(Z1 ,··· ,ZT )∈I : Zt ⊆X

T∑
t=1ft (Zt )sparsity constraint

Our
Our contributions
contributions
1

subject to |X| ≤ k
set function representing

the quality of Zt for patch yt

Replacement OMP:

A fast greedy algorithm with approximation ratio guarantees

4/ 9

Dictionary selection with sparsity constraints
Maximize
X⊆Vmax(Z1 ,··· ,ZT )∈I : Zt ⊆XT∑
t=1ft (Zt )sparsity constraint

Our
Our contributions
contributions
1

Replacement OMP:

2p-Replacement sparsity families:

subject to |X| ≤ k
set function representing

the quality of Zt for patch yt

A fast greedy algorithm with approximation ratio guarantees
A novel class of sparsity constraints generalizing existing ones

4/ 9

1 Replacement OMP
Replacement Greedy for two-stage submodular maximization [Stan+’17]

5/ 9

1 Replacement OMP
Replacement Greedy for two-stage submodular maximization [Stan+’17]
1st result application to dictionary selection
Replacement GreedyO(s2 dknT) running time

5/ 9

1 Replacement OMP
Replacement Greedy for two-stage submodular maximization [Stan+’17]
1st result application to dictionary selection
Replacement GreedyO(s2 dknT) running time

2nd result O(s2 d) acceleration with the concept of OMP
Replacement OMP

O((n + ds)kT) running time

5/ 9

1 Replacement OMP
algorithmapproximation
ratio

running
time

empirical

performance

SDSMA [Krause–Cevher’10]
SDSOMP [Krause–Cevher’10]
Replacement Greedy
Replacement OMP

6/ 9

2 p-Replacement sparsity families
average sparsity⊆[Cevher–Krause’11]
average sparsity⊆

w/o individual sparsity⊆

block sparsity[Krause–Cevher’10]

individual sparsity[Krause–Cevher’10]⊆

individual matroids[Stan+’17]

7/ 9

2 p-Replacement sparsity families(3k − 1)-replacement sparse

average sparsity(2k − 1)-replacement sparse⊆[Cevher–Krause’11]
average sparsity⊆block sparsity[Krause–Cevher’10]⊆k-replacement sparse

w/o individual sparsity

individual sparsity[Krause–Cevher’10]⊆individual matroids[Stan+’17]

7/ 9

2 p-Replacement sparsity families
We extend Replacement OMP to p-replacement sparsity families
TheoremReplacement OMP achieves
if I is p-replacement sparse

m22s 

2Ms,2



M
1 − exp − pk ms,2 -approximation
2sAssumptionft (Zt ) =△max

wt : supp(wt )⊆Zt

ut (wt )where ut is m2s -strongly concave on Ω2s = {(x, y): ∥x − y∥0 ≤ 2s}
and Ms,2 -smooth on Ωs,2 = {(x, y): ∥x∥0 ≤ s, ∥y∥0 ≤ s, ∥x − y∥0 ≤ 2}

8/ 9

Overview
1Replacement OMP: A fast algorithm for dictionary selection

2p-Replacement sparsity families: A class of sparsity constraints

Other
Other contributions
contributions
Empirical comparison with dictionary learning methods
Extensions to online dictionary selection

Poster #78 at Room 210 & 230 AB, Thu 10:45–12:45

9/ 9