Tree structured sparse coding on cubes
Authors: Arthur Szlam
ICLR 2013

Abstract: A brief description of tree structured sparse coding on the binary cube.

arXiv:1301.3590v1  [cs.IT]  16 Jan 2013
Tree structured sparse coding on cubes
Arthur Szlam
City College of New York
aszlam@ccny.cuny.edu
Several recent works have discussed tree structured sparsecoding [8, 10, 7, 3], where N data points
in Rd written as the d × N matrix X are approximately decomposed into the product of matrices
W Z. Here W is a d× K dictionary matrix, andZ is a K× N matrix of coefﬁcients. In tree structured
sparse coding, the rows of Z correspond to nodes on a tree, and the columns of Z are encouraged to
be nonzero on only a few branches of the tree; or alternatively, the columns are constrained to lie on
at most a speciﬁed number of branches of the tree.
When viewed from a geometric perspective, this kind of decom position is a “wavelet analysis” of
the data points in X [9, 6, 11, 1]. As each row in Z is associated to a column of W , the columns
of W also take a tree structure. The decomposition corresponds t o a multiscale clustering of the
data, where the scale of the clustering is given by the depth i n the tree, and cluster membership
corresponds to activation of a row in Z. The root node rows of Z corresponds to the whole data
set, and the root node columns of W are a best ﬁt linear representation of X. The set of rows of Z
corresponding to each node specify a cluster- a data pointx is in that cluster if it has active responses
in those rows. The set of columns of W corresponding to a node specify a linear correction to the
best ﬁt subspace deﬁned by the nodes ancestors; the correction is valid on the corresponding cluster.
Here we discuss the analagous construction on the binary cube {− 1,1}d. Linear best ﬁt is replaced
by best ﬁt subcubes.
1 The construction on the cube
1.1 Setup
We are given N data points in Bd = {− 1,1}d written as the d × N binary matrix X. Our goal is to
decompose X as a tree of subcubes and “subcube corrections”. Aq dimensional subcube C = Cc,Ir
of Bd is determined by a point c ∈ Bd, along with a set of d − q restricted indices Ir = r1, ..., rd−q.
The cube Cc,Ir consists of the points b ∈ Bd such that bri = cri for all ri ∈ Ir, that is
Cc,Ir = {b ∈ Bd s.t. bri = cri ∀ri ∈ Ir}.
The unrestricted indices Iu = {1, ..., d} \ Ir can take on either value.
1.2 The construction
Here I will describe a simple version of the construction where each node in the tree corresponds to
a subcube of the same dimension q, and a hard binary clustering is used at each stage. Suppose o ur
tree has depth l. Then the construction consists of
1. A tree structured clustering of X into sets Xij at depth (scale) i ∈ { 1, ..., l} such that
⋃
j
Xij = X,
2. and cluster representatives (that is d − iq-dimensional subcubes)
Ccij ,Ir
ij
1
such that the restricted sets have the property that if ij is an ancestor of i′j′,
Ir
ij ∩ Ir
i′j′ = Ir
ij ,
and
cij(s) =ci′j′ (s)
for all s ∈ Ir
ij
Here each cij is a vector in Bd; the complete set of cij roughly corresponds to W from before.
However, note that each cij has precisely d − iq entries that actually matter; and moreover because
of the nested equalities, the leaf nodes carry all the inform ation on the branch. This is not to say
that the tree structure is not important or not used- it is, as the leaf nodes have to share coordinates.
However once the full construction is speciﬁed, the leaf rep resentatives are all that is necessary to
code a data point.
1.3 Algorithms
We can build the partitions and representatives starting from the root and descending down the tree
as follows: ﬁrst, ﬁnd the best ﬁt d − q dimensional subcube for the whole data set. This is given
by a coordinate-wise mode; the free coordinates are the ones with the largest average discrepancy
from their modes. Remove the q ﬁxed coordinates from consideration. Cluster the reduced ( d − q
dimensional) data using K means with K = 2; on each cluster ﬁnd the best ﬁt (d − q) − q cube.
Continue to the leaves.
1.3.1 Reﬁnement
The terms Ccij ,Ir
ij and Xij can be updated with a Lloyd type alternation. With all of the Xij ﬁxed,
loop through each C from the root of the tree ﬁnding the best subcubes at each scale for the current
partition. Now update the partition so that each x is sent to its best ﬁt leaf cube.
1.3.2 Adaptive q, l, etc.
In [1], one of the important points is that many of the model pa rameters, including the q, l, and
the number of clusters could be determined in a principled wa y. While it is possible that some of
their analysis may carry over to this setting, it is not yet done. However, instead of ﬁxing q, we can
ﬁx a percentage of the energy to be kept at each level, and choo se the number of free coordinates
accordingly.
2 Experiments
We use a binarized the MNIST training data by thresholding to obtain X. Here d = 282 and
N = 60000. Replace 70% of the entries in X with noise sampled uniformly from {− 1,1}, and
train a tree structured cube dictionary with q = 80and depth l = 9. The subdivision scheme used to
generate the multiscale clustering is 2-means initialized via randomized farthest insertion [2]; this
means we can cycle spin over the dictionaries [5], to get many different reconstructions to average
over. In this experiment the reconstruction was preformed 5 0 times for the noise realization. The
results are visualized below.
References
[1] W. Allard, G. Chen, and M. Maggioni. Multiscale geometric methods for data sets II: Geomet-
ric multi-resolution analysis. to appear in Applied and Computational Harmonic Analysis.
[2] David Arthur and Sergei Vassilvitskii. k-means++: the a dvantages of careful seeding. In Pro-
ceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA ’07,
pages 1027–1035, Philadelphia, PA, USA, 2007. Society for I ndustrial and Applied Mathe-
matics.
[3] Richard G. Baraniuk, V olkan Cevher, Marco F. Duarte, and Chinmay Hegde. Model-Based
Compressive Sensing. Dec 2009.
2
Figure 1: Results of denoising using the tree structured cod ing. The top left image is the ﬁrst 64
binarized MNIST digits after replacing 70% of the data matrix with uniform noise. The top right
image is recovered, using a binary tree of depthl = 9and q = 90, and 100 cycle spins, thus the non-
binary output, as the ﬁnal result is the average of the randomclustering initialization (of course with
the same noise realization). The bottom left image is recovered using robust pca [4], for comparison.
The bottom right is the true binary data.
3
[4] Emmanuel J. Cand` es, Xiaodong Li, Yi Ma, and John Wright. Robust principal component
analysis? J. ACM, 58(3):11, 2011.
[5] R. R. Coifman and D. L. Donoho. Translation-invariant de -noising. Technical report, Depart-
ment of Statistics, 1995.
[6] G. David and S. Semmes. Singular integrals and rectiﬁabl e sets in Rn: au-del` a des graphes
Lipschitziens. Ast´erisque, 193:1–145, 1991.
[7] Laurent Jacob, Guillaume Obozinski, and Jean-Philippe Vert. Group lasso with overlap and
graph lasso. InProceedings of the 26th Annual International Conference onMachine Learning,
ICML ’09, pages 433–440, New York, NY , USA, 2009. ACM.
[8] R. Jenatton, J. Mairal, G. Obozinski, and F. Bach. Proxim al methods for sparse hierarchical
dictionary learning. In International Conference on Machine Learning (ICML), 2010.
[9] P. W. Jones. Rectiﬁable sets and the traveling salesman p roblem. Invent Math, 102(1):1–15,
1990.
[10] Seyoung Kim and Eric P. Xing. Tree-guided group lasso fo r multi-task regression with struc-
tured sparsity. In ICML, pages 543–550, 2010.
[11] Gilad Lerman. Quantifying curvelike structures of mea sures by using L2 Jones quantities.
Comm. Pure Appl. Math., 56(9):1294–1365, 2003.
4


Peer review:
[Review]:
The paper extends the widely known idea of tree-structured sparse coding to the Hamming space. Instead for each node being represented by the best linear fit of the corresponding sub-space, it is represented by the best sub-cube. The idea is valid if not extremely original. 

I’m not sure it has too many applications, though. I think it is more frequent to encounter raw data residing some Euclidean space, while using the Hamming space for representation (e.g., as in various similarity-preserving hashing techniques). Hence, I believe a more interesting setting would be to have W in R^d, while keeping Z in H^K, i.e., the dictionary atoms are real vectors producing best linear fit of corresponding clusters with binary activation coefficients. This will lead to the construction of a hash function. The out-of-sample extension would happen naturally through representation pursuit (which will now be performed over the cube).

Pros:

1.	A very simple and easy to implement idea extending tree dictionaries to binary data
2.	For binary data, it seems to outperform other algorithms in the presented recovery experiment. 

Cons:

1.	The paper reads more like a preliminary writeup rather than a real paper. The length might be proportional to its contribution, but fixing typos and putting a conclusion section wouldn’t harm.
2.	The experimental result is convincing, but it’s rather andecdotal. I might miss something, but the author should argue convincingly that representing binary data with sparse tree-structured dictionary is interesting at all, showing a few real applications. The presented experiment on binarized MNIST digit is very artificial.