User suresh venkat - MathOverflow

Exponential (or other) families of distributions on manifolds.

2011-10-28T17:53:30Z

The exponential family is a general parametrized class of probability distributions on $R^n$ that has many nice properties (ML estimation among them) and includes most of the "standard" distributions one encounters (Gaussian, multinomial, exponential, $\chi^2$ etc).

Are there similarly well-defined parametrized families of distributions for manifold-valued random variables ? Specifically, if you have a general Riemannian manifold ? Or asked another way, is there an equivalent notion of an "exponential family" for a Riemannian manifold ?

Answer by Suresh Venkat for An optimization problem, non complete bipartite graph and hungarian algorithm

2012-11-30T04:25:03Z

There's a standard trick to convert the min cost matching problem on a balanced bipartite graph to one on an unbalanced bipartite graph. Let $G = (X \cup Y, E, w)$ be the bipartite graph where $E \subset X \times Y$ and $|X| \le |Y|$.

Now create a copy of $G$ and add it "reversed", so that in the new graph both sides have exactly $|X| + |Y|$ vertices. All old edges have their same weight: edges between vertices in $X$ and their copies have weight $\infty$, and edges between vertices in $Y$ and their copies have weight zero.

Now run the usual algorithm, and the solution will have cost exactly twice the unbalanced cost.

p.s the fact that the graph is not complete is irrelevant - you can always pretend that there are dummy edges with infinite weight.

While the above method works, it's inefficient. there's a recent (2012) paper by Ramshaw and Tarjan on exactly this problem.

2-Coloring a planar hypergraph

2012-11-17T00:10:47Z

Consider a hypergraph (of rank 3) $H = (V, E)$ (where the rank of $H$ is the maximum cardinality of a hyperedge). $H$ is said to be planar if we can construct a planar graph $G = (V, A)$, and a mapping $f$ from $E$ to the faces of $G$ such that $v \in E$ iff $v$ is adjacent to $f(E)$ in the drawing.

Further, a hypergraph is said to be 2-colorable if there is an assignment of the colors R, B to the vertices so that no edge is monochromatic.

It is known that $2$-coloring a hypergraph of rank 3 is NP-complete.

Is there anything known about the complexity of 2-coloring a planar hypergraph of rank 3 ?

Known graph/surface invariants that can be extracted from homology over different fields

2012-03-29T22:34:31Z

The $Z_2$-homology of a surface viewed as a simplicial complex allows us to extract interesting invariants from the resulting homology groups. $\beta_0$ is the number of connected components, $\beta_1$ is the number of "tunnels" and $\beta_2$ is the number of "cavities" ($\beta_i$, the $i^{th}$ Betti number, being the rank of the $i^{th}$ homology group)

Are there other "interesting" invariants of surfaces (or even graphs) that can be obtained by going from $Z_2$ to some other field (like the rationals), or are all of these equivalent in some sense ?

Answer by Suresh Venkat for Finding optimal vertex partitioning of graphs to maximize cohesion and minimize coupling

2011-12-27T04:49:39Z

I'm not sure where in your formulation you use the directed nature of the graphs. However, if that's not a critical point, correlation clustering is a clean formulation that captures this: You're given a weighted graph and the goal is to find a partitioning so that you maximize (the sum of weights for intra0cluster edges - sum of weights of intercluster edges). There are simple approximation algorithms for this problem (see the references here)

Different ways of proving that two sets are equal

2010-02-26T18:09:42Z

I'm not sure if this is a soft question, or should be community wiki.

I was explaining to a student how to prove that two sets were equal using what I called the 'oldest trick in the book': to show that $A = B$, prove $A \subseteq B$ and $B \subseteq A$. This got me thinking: what are the other ways of showing that two sets are equal. There's of course the bijection method (establish a 1-1 onto correspondence), but I couldn't think of others off the top of my head.

Are there many more general-ish techniques for proving two sets equal ?

Answer by Suresh Venkat for finding numbers at k hamming distance

2011-02-15T08:10:48Z

If you're willing to live with approximations, then the standard approach to near-neighbor search (or in your case fixed radius search) in a Hamming space is by using locality-sensitive hashing. Your case is even simpler because you know the radius you're concerned with. Alternatives include the method by Kushilevitz, Ostrovsky and Rabani.

Analogy of Parseval identity for Legendre Transform ?

2011-02-02T23:17:34Z

Parseval's identity states that the sum of squares of coefficients of the Fourier transform of a function equals the integral of the square of the function, or

$$ \sum_{-\infty}^{\infty} |c_n|^2 = (1/2\pi)\int^\pi_{-\pi} |f(x)|^2 dx $$ where the $c_i$ are the Fourier coefficients.

The Legendre-Fenchel transform can be viewed as a generalization of the Fourier transform. For a given function $f : X \rightarrow R$ over a vector space $X$ which has dual $X^{*}$ , the transform $f^* : X^* \rightarrow R$ is defined as: $$ f^*(p) = \sup_{x \in X}\ \langle x, p\rangle - f(x) $$ where further $p = f'(x)$ is denoted as $x^*$ . So my question is: Is there any natural generalization of Parseval's identity to relate $f^*$ and $f$ ? To be specific, I'm trying to relate quantities like $\|x-y\|$ to $\|p - q\|$ where $p = x^*, q = y^*$

Answer by Suresh Venkat for Algorithm for k-medians in a convex polygon

2010-12-22T10:11:57Z

The problem you're asking about (for $k=1$) is called the continuous Fermat-Weber problem. The primary work on this that I'm aware of is the 2003 paper by Fekete, Mitchell and Beurer. While they examine this problem, they focus on the $\ell_1$ plane (the analytics are easier) and also pay more attention to the $k=1$ case, while also discussing some hardness results.

My $.02$ is that there should be some way of getting an approximation by discretizing the region - it's not clear to me that convexity helps a lot though.

Classes of graphs for which isospectrum implies isomorphism ?

2010-12-13T08:31:35Z

The spectrum of a graph is the (multi)set of eigenvalues of its adjacency matrix (or Laplacian, depending on what you're interested in). In general, two non-isomorphic graphs might have the same spectrum.

Prompted in part by this discussion on reverse engineering a graph from its spectrum, I was wondering:

Are there interesting classes of graphs for which isospectrality implies isomorphism ?

Answer by Suresh Venkat for Idiosyncratic characterizations of $\ell^p$, for $p\not=1,2,\infty$

2010-12-13T09:00:03Z

$p$-stability singles out $0 < p \le 2$. Specifically, there is no probability distribution $P$ such that the linear combination $\sum^n a_i X_i$ is distributed as $\|a\|_p Y$, where $X_1 ... X_n$ and $Y$ are random variables distributed according to $P$, if $p$ is not in the range $(0, 2]$.

For $p = 0.5, 1, 2$ these distributions have closed-form expressions.

(note: updated to reflect Gideon Schectman's comment)

The "girthwidth" of a graph

2010-12-03T17:29:02Z

Abstractly, tree/path decompositions of a graph $G$ can be thought of as doing the following:

fix a "skeleton" class of graphs (tree or path)
Pick a member of this class $H$. Associate with each node of $H$ a subset of vertices of $G$ such that (1) For each edge $e = (u,v)$ in $G$, there exists a node of $H$ containing both $u$ and $v$ and (2) the set of nodes of $H$ containing a fixed vertex of $G$ form a connected subgraph
minimize the maximum cardinality of the set associated with a node of $H$, over all such associations and skeletons.

Suppose that rather than choosing a tree or a path, we are allowed to pick any graph of girth at least $g$, for some fixed parameter $g$. Is there anything known about the resulting "girthwidth" of a graph ?

Answer by Suresh Venkat for Optimal binary code for points in a metric+probability space

2010-11-17T06:09:33Z

The problem you're trying to solve is a generalization of what is called the 'continuous $k$-median problem'. In that problem, the center locations are arbitrary, whereas in your case, they are on a grid. However, your problem starts with an arbitrary metric space. While the cited problem is NP-hard, and is likely to remain so for your problem, there are useful heuristics that you can try for the case when $X = {\mathbb R}^n$, including $k$-means-style methods.

For example, you could fix a collection of centers on the grid, compute the Voronoi diagram, integrate your density within each cell to find the "average" location, and then "snap" this location to the nearest grid cell and repeat.

Planar layouts of bipartite graphs

2010-11-07T21:05:01Z

Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar.

It would be very convenient if there was a planar layout that had all the variable vertices in one line and all the clause vertices in a straight line. This can't be done because such a graph would be outerplanar, and $K_{2,3}$ isn't.

But maybe a weaker layout is possible.

Is it possible to lay out any planar bipartite graph $G = (A \cup B, E)$ such that

All vertices of $B$ are on a straight line

A can be partitioned into $A_1 \cup A_2$ such that all vertices of $A_1$ are on a parallel straight line to the left of $B$, and all vertices of $A_2$ are on a parellel straight line to the right of $B$.

This seems to relate to track drawings of planar graphs.

Answer by Suresh Venkat for Relationship between these two probability mass functions.

2010-11-05T00:52:23Z

I'm not sure how interesting this is, but in the first case, straight multiplication yields that $E[X] = \lambda$, and $E[Y] = E[X^2]/\lambda$, which allows you to bound the second moment of $X$ in terms of $E[Y]$.

Answer by Suresh Venkat for Maximum average value within a rectangular bounding box

2010-10-15T05:54:31Z

While your question as stated seems ill-formed (as commenters point out, the optimal solution is a 1x1 box around the maximum value), let's assume that there's some other constraint (MxN is too large for example, or there's a lower bound on the size of the query box) that makes this approach infeasible.

In that case, at least for approximations, and if MxN is very large, an approach based on $\epsilon$-approximations might work for you. Roughly speaking, you're trying to do range querying over a set of ranges that are "well structured" (formally, have low VC-dimension) and you'd like to extract a sample of the input so that range queries on this sample approximate range queries on the real input. It turns out that a random sample of the input of size roughly $O(1/\epsilon^2 \log 1/\epsilon)$ would suffice to estimate the ranges within error $\epsilon$. Algorithmically, then you merely implement your expensive procedure on this small sample, and presumably that would be more efficient.

Answer by Suresh Venkat for Preferred embedding of finite metric spaces in riemaniann manifolds of given dimension

2010-10-14T20:14:20Z

This is almost certainly not what you want, but it illustrates why you need a tighter specification of 'preferred'.

Any $n$-point metric space can be embedded isometrically in $\ell_\infty^n$.

Proof: (this is a well known result): Let the $r^{th}$ coordinate of $x_j$ be the distance from $x_i$ to $x_r$. BY triangle inequality, we know that for any triple $i,j,k$, $$ d(x_i,x_j) - d(x_k, x_j) \le d(x_i, x_k) $$ which establishes the correctness of the embedding.

One interesting notion of preferred therefore might be that the target space dimension is either independent of $n$, or at the very least depends sublinearly on $n$.

Higher-order dimension in posets: a reference request

2010-10-11T22:38:30Z

Let $P = (X, \le)$ be a partially-ordered set. Then the dimension of $P$ is the minimum number of total orders over $X$ whose intersection yields $P$. Alternately, the dimension of $P$ is the minimum dimension of an isomorphic embedding of $P$ into $R^d$ endowed with the dominance partial order: $(x_1, \ldots x_d) \preceq (y_1, \ldots, y_d)$ if for all $i$, $x_i \le y_i$.

The set of total orders (the realizers) that witness the dimension can be thought of as witnessing all possible legal pairwise orderings in any linear extension of $P$: if $a, b$ are not comparable in $P$, then both $a\le b$ and $a \ge b$ must be witnessed by realizers.

There is a higher-order generalization of the dimension, defined as follows. Fix a parameter $r < |X|$. Then the $r$-dimension of $P$ is the minimum number of total orders that witness all legal ordering relationships among $r+1$-tuples of elements in $P$.

For example, the trivial poset $\{a,b,c\}$ (no orderings) has dimension two via the two orderings $a,b,c$ and $c,b,a$. However, this poset has a 2-dimension of 6, because we need all the $3!=6$ orderings of the three elements.

Question:

Is there any known geometric interpretation of the $r$-dimension like what we have for the dimension ?

Are there known bounds on the $r$-dimension ? For example, we know that the dimension is upper bounded by the width (and this is a fairly weak bound in general).

Vector-valued valuations on lattices

2010-06-04T15:56:13Z

There's a fair amount of work on valuations on (modular) lattices, by which I mean functions $v : \mathcal{L} \rightarrow R$ that satisfy the modular expression $$v(x) + v(y) = v(x \wedge y) + v(x \vee y) $$

I'm wondering if there's been any work on vector-valued valuations (where the range of v is $R^k$ and the same relation holds) ?

In addition, I'm also interested in lower valuations (I'm not sure if this name is standard) that satisfy the submodular inequality $$v(x) + v(y) \ge v(x \wedge y) + v(x \vee y) $$ and possibly the generalization to $R^k$ where we replace the above by $$v(x) + v(y) \succeq v(x \wedge y) + v(x \vee y) $$ ($\succeq$ being the coordinate-wise partial order)

This is a reference request, for the most part.

Constructing a metric over a lattice

2010-02-21T06:45:47Z

Consider a lattice $({\cal L}, \wedge, \vee)$ with an antimonotonic function $f: {\cal L} \rightarrow {\mathbb R}$ defined on it (i.e $x \preceq y \implies f(x) \ge f(y)$).

$f$ is said to be submodular if for all $x,y \in {\cal L}$, $$f(x) + f(y) \ge f(x \wedge y) + f(x \vee y)$$ and supermodular if the inequality is flipped (again for all $x,y$).

It's generally known (there's an easy proof), that a submodular $f$ induces a metric on ${\cal L}$ via the defn $$ d_s(x,y) = 2f(x \wedge y) - f(x) - f(y)$$. If $f$ is supermodular, then the construction $$d^s(x,y) = f(x) + f(y) - 2f(x \vee y)$$ yields a metric.

Question I'm dealing with an $f$ that is nether sub- nor supermodular. I can define the "distance" $$ d(x,y) = \min ( d^s(x,y), d_s(x,y))$$

Conjecture: $d(x,y)$ is a metric.

I have very little sound mathematical intuition for why this conjecture should be true, and bucketloads of empirical evidence (from a lattice I'm actually working with). This seems like the kind of thing that if true, would be reasonably well known to experts, and if false, might have a clear counterexample. So this is a plea for help.

Since it might make a difference, I should mention that the lattice I'm working with is nondistributive in general, but it has distributive sublattices where I'm still unable to prove the conjecture.

Answer by Suresh Venkat for Analyzing Weighted Set-Cover variant

2010-10-07T05:07:59Z

Rather than focusing on the greedy algorithm, you could also look at the LP formulation. Let's take the specific cost function that you provide. Notice that each element of A is charged $k_1$ if it appears at all in the cover, and each element of $D$ is charged $-k_2$ if it appears in the cover.

Given that, and the fact that you have to cover all elements in $D$, it means that you're going to incur a fixed cost of $-k_2 |D|$ regardless of what else you do, so you might as well ignore it for the purpose of finding the solution.

This leaves the elements in $A$. Set up an LP where there's an indicator variable $x_S$ for each set $S$ as usual, and a variable $y_a$ for each element $a \in A$. Now your cost function can be written as $$ C = k_1\sum y_a - \sum |S| x_S $$ subject to the constraints $$\forall S, 0 \le x_S \le 1$$ $$ \forall a, S \text{ contains } a, x_S \le y_a$$ Notice that the second constraint ensures that you have to charge a cost to $y_a$ if you pick any of the sets that contain it. The minimization of $C$ ensures that you'll always pick $y_a = x_S$ for some $S$.

At this point you have either an LP-rounding problem to solve (and you can look at standard ways of solving set-cover-ish LPs via rounding), or you can think of the primal-dual formulation, which essentially leads to greedy in any case.

Answer by Suresh Venkat for Nodes clusters with a distance matrix

2010-09-16T05:26:22Z

Where do the distances in $M$ come from ? this is somewhat important. for example, is it guaranteed that $M$ is a metric (i.e satisfies triangle inequality) ? Further, are the distances simple Euclidean distances ? As an aside, how can you even run $k$-means ? $k$-means requires a vector space, so that centroids are well defined. In your example, you appear to be considering a discrete distance space.

While $k$-means and spectral clustering (which is really spectral dimensionality reduction followed by $k$-means) are fine algorithms, possibly a more important question to ask is: what kind of measure do you want to optimize ? $k$-means tries to (but doesn't) minimize the sum of squared distances between points in a cluster and their centroid.

In your example, you could ask for the $k$-clustering that minimizes the maximum radius of a cluster, where the radius is defined as $r = \min_{p \in C} \max_{q \in C} d(p,q)$. This is easy to approximate within a factor of 2 by picking $k$ maximally separated points.

Answer by Suresh Venkat for What is the easiest randomized algorithm to motivate to the layperson?

2010-09-10T05:30:14Z

While this requires the use of approximation as well as randomization, I always find the idea that you can get a good estimate of a population by sampling a constant sized set to be very non-intuitive and powerful. The way I usually phrase it in class is: you want to poll the population so that any reasonably popular group is represented. If "reasonably" popular" is defined as a constant fraction, then you only need to sample a constant number of people to hit all groups. Judging by how the general population gets confused by polls, this seems like a good example.

Another example that's more useful for a "CS-aware" layperson is one that requires knowledge of the notion of a median. You can get a quick and dirty approximation for the median in constant time by sampling (in fact, the median of THREE random elements suffices), and the more you sample, the better the approximation.

Probably the most spectacular demonstration of the power of randomness, but one alas that isn't easy to prove to a layman, is the power of two choices. It seems almost impossible that it's true, but it is.

Answer by Suresh Venkat for Permutations with identical objects

2010-08-31T05:37:26Z

Here's a sketch of an idea. Consider first the problem of computing the number of permutations of $k$ elements given the number of elements $n_i$ in each class. This is easy: it works out to $$\frac{k!}{\Pi_i n_i !}$$ because in any fixed string, you can permute the elements in a class without changing the string.

Now consider the problem of writing down the different partitions of $k$ into the sum of $x$ labelled numbers. Merely finding the sum itself can be done by determining the coefficient of $y^k$ in the polynomial $$ \Pi_i \frac{y^{r_i+1}-1}{y-1}$$

But this is not enough, since you need to weight each such partition by a different number. However, we know that the contribution of $y^i$ must be $1/i!$, so the overall number we are looking for is $k!$ times the coefficient of $y^k$ in the polynomial $$ \Pi_i \sum_{j=0}^{r_i} \frac{y^j}{j!}$$

Answer by Suresh Venkat for Suggest effective heuristic (not precise) graph colouring algorithm

2010-08-24T05:25:12Z

There are a number of heuristics that work fairly well. They all work by prescribing some kind of ordering on the vertices, and then coloring the vertices one by one, using the least unused color to color the next one.

First Fit does precisely the above, with an arbitrary initial ordering. It's fast, but needless to say performs rather poorly.
LDO orders the vertices in decreasing order of degree, the idea being that the large degree vertices can be colored more easily.
SDO (saturation degree ordering) is a variant on LDO where the vertices are ordered in decreasing order by "saturation degree", defined as the number of distinct colors in the vertex neighborhood.
IDO (incidence degree ordering) is a variant of SDO where the "degree" of a vertex is defined as the number of colored vertices in its neighborhood.

The latter two heuristics require the order to be rebuilt after each step, and so are more expensive, but there's empirical evidence suggesting that they do reasonably well, especially in parallel.

None of these algorithms come with any kind of formal guarantees, so be warned.

Answer by Suresh Venkat for Is the solution bounded Diophantine problem NP-complete?

2010-08-23T02:21:33Z

Seems to me that you could encode SAT in the usual polynomial manner, with variables restricted to being 0 or 1.

Answer by Suresh Venkat for What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))?

2010-08-20T03:29:31Z

Another approach you can take is as follows. Since the closest pair can be solved by $n$ invocations of a nearest neighbor query, you could examine the set of techniques available for performing near-neighbor queries in $n^\epsilon$ time.

In this regard, Ken Clarkson's survey of nearest neighbor methods in metric spaces is quite helpful. Among the things he does is review various properties of metric spaces and how they influence the running time of NN algorithms (the doubling dimension mentioned by David is one example considered here).

Answer by Suresh Venkat for nonasymptotic complexity results

2010-08-20T02:47:55Z

Are you by any chance referring to examples like Haken's proof that the pigeonhole principle requires exponentially long resolution proofs ?

Answer by Suresh Venkat for Why relativization can't solve NP !=P?

2010-08-15T18:11:29Z

I was holding off on posting a non-answer, but am encouraged by JDH.

There's still something deeply puzzling about the idea that if $A = B$, there's possibly an oracle for which $A^O \ne B^O$, and that seems to be at the heart of the OP question. In that respect, ilyaraj's example of IP and PSPACE is actually better, because unlike with P and NP, where we don't know the true answer, we actually KNOW that IP = PSPACE, and yet there's still an oracle that separates them.

But I think a deeper explanation needs to go beyond relativization, to the properties that relativization relies on. The Arora-Barak book explains this quite well: they point out that proofs like diagonalization rely on efficient simulation (universality) and the ability to list out machines (enumeration), and that any oracle-based result relies ONLY on these two properties.

Thus, the real answer to why P vs NP is independent of relativized arguments is that you need to exploit more information than just universality and enumeration. This comes to mind precisely because of the "new" barrier coming out the Deolalikar proof discussions, that proof techniques that try to differentiate the geometry of solutions to SAT vs P-time problems can't work.

Answer by Suresh Venkat for Most 'obvious' open problems in complexity theory

2010-08-14T00:32:35Z

GI $\in$ P. We know that there are bad consequences if GI is NP-complete,

p.s GI is graph isomorphism

Comment by Suresh Venkat

2012-11-18T05:43:44Z

I see. the problem is that a rank three hypergraph will have edges of size 2 as well (in fact these are used in the NP-completeness for general hypergraphs)

Comment by Suresh Venkat

2012-11-18T05:42:10Z

It's not about coloring planar graphs per se (see Brendan McKay's answer)

Comment by Suresh Venkat

2012-09-11T05:46:55Z

For example, this paper: arxiv.org/abs/1006.3585 that constructs the associated matrices using bounded independence hash functions.

Comment by Suresh Venkat

2012-09-11T05:45:48Z

There are derandomized constructions of the matrices involved in the JL projection, if that's something that interests you.

Comment by Suresh Venkat

2012-09-06T07:09:37Z

If you're in a low dimensional space, then your problem reduces to performing a set of point location queries in a farthest-point Voronoi diagram under the appropriate metric.

Comment by Suresh Venkat

2012-09-06T07:07:32Z

This is not quite facility location because you're not "searching" for facilities in the OP's question - you're given the facilities (the set A)

Comment by Suresh Venkat

2012-08-22T22:39:16Z

This seems like an ideal counterpoint to Hardy's Lament. I'm calling it Thurston's Paean :). Seems poignant now that he has passed.

Comment by Suresh Venkat

2012-03-30T02:10:50Z

So you're saying that they are all equivalent ?

Comment by Suresh Venkat

2011-12-22T05:40:06Z

Note that this construction is almoot identical to the construction that induces the Mahalanobis distance between two vectors, when M is positive definite.

Comment by Suresh Venkat

2011-12-07T05:52:27Z

But the hamming distance satisfies the triangle inequality.

Comment by Suresh Venkat

2011-10-29T20:58:57Z

Thanks. I'll check out both these references. The first one in particular has some elements that seem useful.

Comment by Suresh Venkat

2011-10-29T20:57:26Z

@Suvrit that is correct. You can get one kind of normal distribution equivalent using the heat kernel.

Comment by Suresh Venkat

2011-10-28T22:03:00Z

Hi Joe, I'm specifically looking for random vars whose values are points on a manifold. @Deane, information geometry (which I'm familiar with) deals with how to represent families of distributions as manifolds (or submanifolds), which is different to building a probability distribution ON a manifold.

Comment by Suresh Venkat

2011-10-28T18:24:43Z

I guess my question isn't so much "can it be done" as much as "has it been done for any specific settings and what references do I need to look at". In particular, in the context of statistical estimation .

Comment by Suresh Venkat

2011-09-12T07:33:25Z

A book that needs to be updated, but was perfect at the time, was Structural Complexity by Balcazar, Diaz and Gabarro: books.google.com/books/about/…