Timeline for Do Isometry Groups Tell Us How Difficult Norms are to Compute?
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2010 at 1:53 | comment | added | Qiaochu Yuan | @Nathaniel: start with the unit ball in R^n, pick three points lying slightly outside it, fairly close together, and in general position, and take the convex hull and then the "central closure" (I hope it is clear what I mean by this) of the result. This defines a norm with trivial isometry group which I think should be easily computable: if the points are spaced sufficiently far apart relative to their distance from the ball then one has just stuck some conical caps onto the unit ball, which are easy to work with. | |
| Dec 2, 2010 at 1:05 | history | edited | Nathaniel Johnston | CC BY-SA 2.5 |
deleted 3 characters in body
|
| Dec 2, 2010 at 0:28 | comment | added | Nathaniel Johnston | @Ryan and Qiaochu: Ah, thank you for the clarification. This doesn't contradict the conjecture though, does it? I would expect that computing any norm with trivial isometry group is in fact NP-HARD, which would be OK. | |
| Dec 2, 2010 at 0:07 | comment | added | Qiaochu Yuan | @Yemon: good point. @Nathaniel: a norm on R^n is determined by its unit ball, which (relative to the standard basis of R^n) is constrained only by the properties of being closed, centrally symmetric, and convex. As Yemon Choi points out, the only symmetry required of this convex body is the central symmetry, and otherwise this convex body need not have any other symmetries. It shouldn't be hard to come up with examples from here. | |
| Dec 2, 2010 at 0:04 | comment | added | Ryan Budney | Qiaochu likely refers to trivial in this sense: springerlink.com/content/3k177212070313x5 | |
| Dec 1, 2010 at 23:21 | comment | added | Yemon Choi | Qiaochu: multiplication by $\pm1$ is always an isometry | |
| Dec 1, 2010 at 23:11 | comment | added | Nathaniel Johnston | By matrix norm I just mean any norm on matrices (so it's nonnegative, positive scalars pull out, and it satisfies the triangle inequality -- I don't even require the submultiplicativity property holds). Really you could just think of it as a norm on any old finite-dimensional vector space if you prefer. I'm not aware of any norms with trivial isometry group though (perhaps I'm being dense) -- could you provide an example? | |
| Dec 1, 2010 at 23:05 | comment | added | Qiaochu Yuan | No, I mean actually trivial. Or is there more to the definition of matrix norm than I thought? | |
| Dec 1, 2010 at 22:56 | comment | added | Nathaniel Johnston | I assume that by the "trivial isometry group" you mean the isometry group of the Frobenius norm (i.e. the unitaries)? If so, then that's actually the only "common" norm with that isometry group. The operator norm's isometry group is generated by multiplication on the left and right by unitaries and the transpose map (which is smaller than the entire unitary group). The isometries for the induced p-norms are a bit messy to describe, but they too are proper subgroups of the unitary group. | |
| Dec 1, 2010 at 22:50 | comment | added | Qiaochu Yuan | Aren't there plenty of norms with trivial isometry group? | |
| Dec 1, 2010 at 22:44 | history | asked | Nathaniel Johnston | CC BY-SA 2.5 |