0
$\begingroup$

I came across a clustering algorithm, which uses the set builder notation to specify the clusters (or elements in the cluster). The algorithm is here.

The following is copied directly from the source, where the optimization function is this:

$$\mathit{E}(\mathbf{Z}) = \sum_{j=1}^k \frac{\mathbf{z}^⊤_j \mathbf{Az}_j}{f_j(\mathbf{Z})}$$

where:

$\mathbf{A} \in \mathbb{R}^{n×n}$ is the affinity matrix of n data points

$\mathbf{Z} = [\mathbf{z_1},···,\mathbf{z_k}] \in \mathcal{Z}, \mathcal{Z} = \{\mathbf{Z} \in \{0, 1\}^{n×k} | \mathbf{Z1} = \mathbf{1}\}$ is an assignment matrix, in which k is the number of clusters and 1 is the all-one vector

The optimization function and the affinity matrix $\mathbf{A}$ are logical, however, when you come to the notation of the clusters Z is where the problem lies. I'm not sure what the following notations mean:

  1. The equation for $\mathcal{Z}$ is based on the predicate $\mathbf{Z1} = \mathbf{1}$, what does that mean? And why do the clusters $\mathbf{Z}$ belong to $\mathcal{Z}$ while $\mathcal{Z}$ is constructed by $\mathbf{Z}$ that belong to the $\{0, 1\}^{n×k}$ set?
  2. The "all-one" vector is what? Presumably a row or column vectors of all 1s?

Thank you.

$\endgroup$
1
$\begingroup$

$\mathbf{Z}$ is an $n \times k$ matrix, and the first $\mathbf{1}$ is a $k \times 1$ matrix (column vector) of 1s (often written as $\mathbf{e}$). The second $\mathbf{1}$ is an $n \times 1$ matrix (column vector) of 1s, and $\mathbf{Z 1} = \mathbf{1}$ means $$\sum_{j=1}^k Z_{i,j} = 1$$ for $i \in \{1,\dots,n\}$. Because $Z_{i,j} \in \{0,1\}$, this implies that each row $i$ contains exactly one 1 and exactly $k-1$ 0s.

$\endgroup$
2
  • $\begingroup$ Hmm I see, if $\mathbf{Z}$ is a $n \times k$ matrix, then are all components of $\mathbf{Z}$ i.e. $\mathbf{z_1},···,\mathbf{z_k}$ $n \times 1$ matrices? So $\mathbf{z_1}$ is $n \times 1$? $\endgroup$ – simplename Nov 27 '20 at 5:33
  • $\begingroup$ Yes, those are $n\times 1$. $\endgroup$ – RobPratt Nov 27 '20 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.