Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It is well known that the nerve (or Čech complex) of a covering consisting of metric balls with a common fixed radius is nicely approximated by the Vietoris-Rips complex. Being a flag complex on its 1-simplices, the latter is computationally much more tractable than the nerve itself.

Does anybody know of other classes of sets that yield approximations to the nerve à la what Vietoris-Rips does for the case of balls? I'm quite open to vague answers, and "approximation" can here certainly mean much poorer ones than Vietoris-Rips.

share|improve this question
    
I would disagree with the well known'. The terms nerve and Cech comlex have a wider and older use than just this. The Wikipedia page is not to be trusted. Vietoris complex is also used in a wider and older meaning for an arbitrary covering. Looking at that Wikipedia entry there are numerous inaccuracies. The Cech complex is not dependent on the embedding. Secondly what do you mean byother classes of sets'? Have you investigated Dowker's paper on the homology of relations? –  Tim Porter Mar 8 '13 at 9:50
    
@Tim Porter: Oh, I certainly didn't mean equate the role of the nerve with that of the VR complex! What I meant to refer to with the Wikipedia link was simply the relationship between the nerve of a cover by metric balls and the corresponding VR complex. I also apologize for the vagueness of the phrase "other classes of sets". I simply meant "something playing the role of balls in the above-mentioned relationship between the VR complex and the nerve". –  gspr Mar 8 '13 at 11:01
add comment

1 Answer 1

up vote 3 down vote accepted

Since the question is rather broad, the answer got unwieldy. Sorry, I hope some of this is relevant to the sort of questions you are asking.

Complexity of Approximating the Čech Complex

The computational tractability of the Vietoris-Rips complex is an engaging - but largely false - contemporary myth. While it is true that testing whether two balls intersect is much easier than testing for higher order intersection, the number of simplices in a Rips complex on $m$ vertices can vary wildly from $m$ for an edgeless $1$-skeleton to a staggering $2^m$ for the complete $1$-skeleton.

A more balanced approach is to build the Čech complex faithfully up to an $n$-skeleton for $n \geq 1$ and then construct the flag complex on top by inserting those higher simplices whose $n$-dimensional faces all exist. Clearly, the traditional Rips complex is the $n=1$ version of such an approximation scheme. At the cost of computing common intersections of $n+1$ balls, one can often drastically reduce the total number of simplices in the approximation-complex. In practice, even $n=2$ provides huge savings of memory over a traditional Rips complex.

Sandwiching of Filtrations

The important thing to note is that "interleaving" or "sandwiching" is an equivalence relation on one-parameter nested families of topological spaces (called filtrations). Consider two such filtrations $X = \lbrace X_a\rbrace_{a > 0}$ and $Y = \lbrace Y_b\rbrace_{b > 0}$. We say that $X$ and $Y$ are $d$-sandwiched for $d \geq 1$ if

$$ X_{a/d} \subset Y_a \subset X_{ad} $$

for each $a \in \mathbb{R}$. Clearly, the Rips and Čech filtrations built with the usual metric balls are $2$-sandwiched. More importantly, if $X$ and $Y$ are $d$-sandwiched, and $Y$ and $Z$ are $e$-sandwiched, then $X$ and $Z$ are $(de)$-sandwiched.

So, the situation is not too exciting in finite dimensional Euclidean space (where Rips and Čech complexes are often built) because all norms are equivalent. No matter which norm you might choose to build balls, there will be some sandwiching between Čech and Rips filtrations, or two different Rips filtrations, or... ? The point is, changing the norm to generate square-shaped balls (for instance) does not achieve too many interesting things in terms of sandwiching, but it might make checking for higher order intersections easier.

The situation is much more exciting in infinite dimensional space, but much less is known I think.

Replacing Balls Entirely

Let $P$ be a finite point set in a normed vector space $(V,\|\cdot\|)$. Let $U = \lbrace U_\epsilon \rbrace_{\epsilon > 0}$ be a filtration of subsets of $V$ all containing $0$, and consider the (filtered) nerve generated by the sets $p + U_\epsilon$ for $p \in P$. We will approximate this filtered nerve $C(U_\epsilon)$ using Rips complexes built out of generic sets (meaning: not necessarily balls).

Let $W = \lbrace W_\epsilon \rbrace_{\epsilon > 0}$ be any other filtration whose sets all contain $0$ and which is $d$-sandwiched with $U$ for some $d \geq 1$. That is, for each $\epsilon > 0$ we have

$$ U_{\epsilon/d} \subset W_\epsilon \subset U_{d\epsilon}.$$

Thus, the Cech filtrations $C(U_\epsilon)$ and $C(W_\epsilon)$ are $d$-sandwiched. But now: the Rips filtration $R(W_\epsilon)$ is $2$-sandwiched with $C(W_\epsilon)$, and hence $2d$-sandwiched with $C(U_\epsilon)$. So, as long as the sets you grow around your point cloud in the Cech and Rips complex have this sandwiching property, you will be able to extract an approximation theorem. In the case where the Cech complex is built using $L^2$-balls $B$, you can get a $2d$-approximation by using a Rips complex built with any sets $U_\epsilon$ so that

$$U_{\epsilon/d} \subset B_\epsilon \subset U_{d\epsilon}$$

for each $\epsilon > 0$.

share|improve this answer
    
Thanks for a very informative answer! –  gspr Mar 8 '13 at 10:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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