mismatches between mathematical essences and data structures

[gusl]

Lately, I've been faced with problems of the following type:
* there are many ways to represent an object
* a canonical representation is either hard to define, or unnatural to work with

(1) optimizing over the space of k-dim linear subspaces (a.k.a. k-flats). They can be represented as bases (more canonically, orthogonal bases), but that's not enough to identify them uniquely. We can define k-flats to be points in a Grassmanian, which is the appropriate quotient space (in which bases of the same space form an equivalence class). But optimizing here involves doing calculus on surfaces, which requires knowledge of differential geometry... or easier, one could use Lagrange multipliers, but I don't have enough constraints (I don't know how to constrain the rotation of the orthogonal basis).

(2) suppose you have an unknown probability distribution over clusterings of nodes. You can easily assign a label to each node such that two nodes are in the same cluster if they have the same label. Of course, these labels are just names, and permuting them results in an equivalent structure, which necessarily has the same probability. Now, suppose you get several samples from this distribution (say, by MCMC), and you want to estimate the distribution. Now, for each sample, you could simply add the other n!-1 relabelings ("mirror images"), but can you do better?
This is known as the "label-switching problem", and in some cases it can addressed by "artificial identifiability constraints" (e.g. in the form of: WOLOG, node 1 is always labeled with "a"), but this too can become unmanageable and unnatural.

Tangentially, is there a nice way to represent graphs modulo isomorphism? I'm aware of spectral techniques (e.g. graph Laplacian), but these are usually lossy, i.e. querying whether two graphs are the "same" (i.e. isomorphic) will result in some false positives.

Comments

[ikeepaleopard]

Graph isomorphism is NP-complete so if you had such a representation, creating an instance for a given graph would have to be Hard.

Graphs

[(Anonymous)]

Forming a canonicalization algorithm for representing graphs modulo isomorphism is clearly at least as hard as checking whether two graphs are, in fact, isomorphic (proof: just run the canonicalizer on both graphs and check if the results are equal).

And the graph isomorphism problem currently has no known polynomial-time solution.

[mdinitz.livejournal.com]

As a theoretician it pains me to do this, but there are some decent algorithms out there for testing graph isomorphism and reducing to a canonical graph. In a previous life, when I was doing combinatorial design theory, I used Brendan McKay's nauty, which does exactly what you asked for -- given a graph, it returns a representation that is canonical up to isomorphism. I have no idea what algorithm it uses, but it was reasonably fast when I used it 7 or 8 years ago.

[(Anonymous)]

is (1) just an example or you actually have some problem which requires some sort of optimization over the space of "k-flats"? if you have such a problem, maybe you can exploit better the structure of it in order to simplify matters. for example, you can characterize the k-th largest eigenvalue of a hermitian matrix as the solution of a certain non-linear min-max problem in which the min is taken over the space of "k-flats" and the max is taken in that space (removing the origin, actually) that's the result of the Courant-Fischer Minimax Theorem, you can take a look at its statement here http://www.cs.tau.ac.il/~haima/gen_cf.pdf

my point is, exploiting the structure of your problem may lead to other more useful characterizations of the solution-set which wouldn't require you to actually try to find a representation for the set of k-flats... there are many different methods to compute eigenvalues...

a propósito, sou eu, Ives...