- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The authors introduce a way of encoding a dataset into a weighted binary sketch and then using that sketch to compute persistence over the dataset. From what I understand, it consists of four steps: (1) The dataset gets mapped to a weighted sparse representation (2) the weighted representation gets mapped to a weighted binary representation (3) Compute the Rips complex over this new binary representation using Hamming distance (4) Use the Max-DTM Rips Filtration to compute persistence. The authors show several associated theoretical results as well, namely, that this new persistence diagram is stable w.r.t. the persistence diagram generated via max-DTM-Rips for the original dataset (in terms of bottleneck distance). They also show that the two persistence diagrams are -interleaved where depends on the maximum distance between any and its assigned cell.
Critical strengths
- The theorem statements seem reasonable and I skimmed through the proofs in the appendix (although I did not read them carefully). I could find no error.
- I found the experiments helpful in increasing my understanding of their theoretical results. In particular, I found figure 2D helpful in understanding how their theorem bound works in practice, it is interesting that the authors observe something in practice that is much better than what their theory predicts.
Critical weaknesses
I think the writing could use some work and the authors could do a better job of contextualizing why their results are important. While topological data analysis is nothing new at ICLR, I think a majority of the ICLR audience is unfamiliar with the concepts in TDA. At several points in the paper, the authors directly use terminology without briefly first explaining the concept. For instance, they do this with DTM throughout the introduction before explaining the concept and why it would be important in the related work.
Furthermore, I still do not fully understand why one would be interested in a binary measure sketch. It seems like one could just directly compute persistence over the weighted representatives instead of taking the extra step of finding a binary sketch.
Questions for authors
- Can the authors clarify why it is necessary to go through the binary encoding step?
- Is there any dependence on dimension in their bounds? For instance, does change as dimension increases?
rebuttal
We thank the reviewer for the review and positive assessment of soundness.
A1: We revised Section 1 to explain motivation and terminology first: recovering components and loops after coordinates cannot be retained or transmitted. DTM is the root mean square distance to the nearest β fraction of probability mass. Together with pairwise distances, it determines filtration entry times, so compression must preserve masses and control geometry. Before the theorems, Figure 1 explains sample → mass-weighted representatives → binary geometry → persistence, and BMS is defined at first use.
A2: We clarified the storage benefit in Section 1 and Section 6: coordinates require Md values, while BMS uses Mb geometry bits, with masses and metadata accounted for separately. Savings can retain more representatives. The state also supports recomputing DTM and persistence for a chosen β after discarding coordinates. Angular or unit-sphere chordal targets need codes and masses; general Euclidean targets additionally need radial information. Figure 2B, main-text Table 2, and the table below give direct evidence: at 4 KiB on Fashion-MNIST, BMS retains M=102, b=256; int8 fits at most five representatives. E7 selects int8 M=1 among all M=1–5 using development error. BMS/int8 mean joint errors are 0.0638/0.3336, with BMS lower in all ten evaluations. The joint-error improvement at this cap directly demonstrates the storage value of binary geometry for the declared topology target. Table R5. Actual allocations and errors on Fashion-MNIST at the 4 KiB cap.
A3: Dimension enters through coverage and storage; perturbation coefficients do not explicitly depend on ambient dimension. At fixed M, isometric embedding preserves rpart, while increased intrinsic complexity can worsen coverage. We added rpart≤2D(C/M)1/s under a covering model in Section 6 and Section N.10, exposing covering dimension s. Figure 11 and Figure 12 separate coordinate growth from changed geometry; Figure 2 adds real high-dimensional data. Coordinate count d can increase storage without changing intrinsic distances, and construction/encoding costs can still depend on d.