Fast greedy algorithms for dictionary selection with generalized sparsity constraints(University of Tokyo)

Replacement OMP returns a solution competitive

with ones obtained by dictionary learning methods.
We extend the algorithms to the online setting.

Dictionary selectionT∑max(Z1,··· ,ZT )∈I : Zt ⊆ X t =1ft (Zt )subject to |X | ≤ kft (Zt ) =△max

wt : supp(wt )⊆ Zt

ut (wt )e.g. ut (wt ) = ∥yt ∥2 − ∥yt − Awt ∥2Haar basis

Db4 basis

Coiﬂet basis+w3≈ w1(Zt )wt ∈t(Z1′ , · · · , ZT′ ) ∈ I | Zt′ ⊆ ZT + a, |Zt \ Zt′ | ≤ 1 (∀t ∈ [T ])argmaxw : supp(w)⊆ Zt

Comparison to dictoinary selection methods (T = 100)©

feasible replacementsut (w) optimal vector for ut with support Zt+w2

approximation ratio

running time

SDSMA [Krause–Cevher’10]

O((k + d)nT )SDSOMP [Krause–Cevher’10]

O (1 / k )O((s + k)sdknT )Replacement Greedy

2 m2s
Ms , 2
1 − exp −Ms2,2m2sO(s2dknT )101100101102103

submodular maxization in [Stan+’17]

We extend SDSMA, Replacement Greedy, and Replacement
OMP to the online setting

SDS_MASDS_OMPRG
RepOMP

0.8

SDS_MASDS_OMPRG
RepOMP

0.6

0.4

0.2

SDS_MASDS_OMPRG
RepOMP

0.8

0.7

0.6

0.5

0.4
0.0
2.5

5.0

7.5

10.0

12.5

dictionary size

15.0

17.5

2.5

20.0

5.0

7.5

10.0

12.5

dictionary size

15.0

17.5

20.0

2.5

5.0residual, synthetic

7.5

10.0

12.5

dictionary size

15.0

17.5

20.0residual, realComparison to dictionary learning methods (T = 1000)
0.8

10SDS_MA
RepOMP
RepOMPd
MODK-SVD

20.7
101010101102SDS_MA
RepOMP
RepOMPd
MODK-SVD
200.6
0.5
0.4
0.3
0.2

SDS_MA
RepOMP
RepOMPd
MODK-SVD

0.45

0.40

0.35

0.30

0.1
0.0
4060

dictionary size

80

20100time, synthetic

4060

dictionary size

80

10020residual, synthetic

4060

dictionary size

80

100residual, real

Experiments on average sparsity

O((n + ds)kT )Replacement Greedy was originally proposed for two-stage+w3102time, synthetic

m1ms
()
1−1/e
M1Ms

Replacement OMP

Zt ⊆ X Atoms for each patch yt (∀t ∈ [T ])+w2

Fa(Z1 , · · · , ZT ) =¦-approx.

Experimental results∗′and let X ← X + a and Zt ← Zt (∀t ∈ [T ])algorithm

X ⊆ V Selected atoms as a dictionary≈ w1tk Ms,2−p m2s

′pp∗- each atom in Zt \ Zt appears at least once in (Zt \ Zt )p′=1′ pp- each atom in Zt \ Zt∗ appears at most once in (Zt \ Zt )p′=1Theoretical results for standard dictionary selection

V Union of existing dictionaries

DCT basis∗
Picka ∈ V that maximizes
T ¦∑©
′maxf(Z) − ft (Zt )(Replacement Greedy)tt′ ,··· ,Z ′ )∈F ∗
(Za t =1T

1¨
T
2

1 ∑(Zt )∇ut wtmax′ \Z′′
ZtM(Z1 ,··· ,ZT )∈Fa∗s,2tt=1«T2∑(Zt )− Ms , 2wt(Replacement OMP)′Z \Z∀(Z1, . . . , ZT ), (Z1∗ , . . . , ZT∗) ∈ I ,′∪′p∃(Z1p , . . . , ZT ) ∈ a∈V Fa(Z1, . . . , ZT ) (p′ ∈ [p]) s.t.

2 Greedy atom selection (Repeat k times)t =1

1 − exp

if I is p-replacement sparse

1 Initialize X := ∅, Zt := ∅ (∀t ∈ [T ])△set function representing the quality of Zt for patch yts,2running time

X ⊆Ve.g. I = (Z1, · · · , ZT ): |Zt | ≤ s

Replacement OMP is M20.8SDS_MA (average)
RepOMP (average)
RepOMPd (average)

running time

Maximizem22s 

test residual variance

We empirically show that in a smaller time,

Theorem

10

SDS_MA (average)
RepOMP (average)
RepOMPd (average)

0.7

2

0.6
0.5
0.4
0.3
0.2

20

4060

dictionary size

80time, synthetic

100

0.375
0.350
0.325
0.300
0.275
0.250

0.1
0.0

SDS_MA (average)
RepOMP (average)
RepOMPd (average)

0.400

test residual variance

p-replacement sparsity families.

Ms,2-smooth on Ωs,2 = {(x, y): ∥x∥0 ≤ s, ∥y∥0 ≤ s, ∥x − y∥0 ≤ 2}

test residual variance

We propose a novel class of sparsity constraints,

ut is m2s-strongly concave on Ω2s = {(x, y): ∥x − y∥0 ≤ 2s} andincluding average/block sparsity [Cevher–Krause’11]

test residual varianceselection, named Replacement OMP.

Assumption
Assumption

A generalized class of sparsity constraints

test residual variance

We propose a fast greedy algorithm for dictionary

p-Replacement sparsity families

test residual varianceReplacement Greedy & Replacement OMP

Our contributions

sparsity constraint

The 32nd Annual Conference on Neural Information Processing Systems

running time

Kaito Fujii & Tasuku Soma

0.225

204060dictionary size

80

residual, synthetic

100

204060dictionary size

residual, real

80100