Tag Archives: mathematics

Linkage

Posted on by

Via Amber, a collection of grassroots feminist political posters from India.

Via John, some fun investigations on how 355/113 is an amazingly good approximation to \pi. Also related are the Stern-Brocot trees, which can give continued fraction expansions.

I had missed this speech by a 10 year old on gay marriage when it happened (I was in India), but it’s pretty heartwarming. For more background on how the principal originally deemed the story “inappropriate.”

What is a Bayesian?

Unrelatedly, ML Hipster — tight bounds and tight jeans.

Advertisement

Linkage

Posted on by

I’m being lazy about more ISIT blogging because my brain is full. So here are some links as a distraction.

Via John, George Boolos’s talk entitled Gödel’s Second Incompleteness Theorem Explained in Words of One Syllable.

D’Angelo is back!

This short video about a subway stair in New York is great, especially the music.

Crooked Timber is on a tear about workplace coercion and its proponents.

Luca’s thoughts on the Turing Centennial are touching.

Linkage

Posted on by

The NIPS deadline is coming up, so I’ve been a bit harried. However, there are many cool things out there on the internet…

IIT Kanpur wants to open an office in the US to recruit faculty.

Via my father, don’t you wonder where the center of mass of a pizza slice is? This is more of an issue for those New York-style fans — in Chicago the deep dish is a little more stable.

A fascinating post from the NY Times about ephemeral islands which appear and disappear as sea levels shift.

Via BK, a musical film about coffee. It’s part of the Jazz Dance Film Fest, which promises to be my undoing, productivity-wise.

An interesting article on the Dalit movement in Maharashtra.

Linkage

Posted on by

Posting has been nonexistent this week due to being busy and incredibly tired. Hopefully the improved spring weather will thaw me out. On the upside, I’ve been reading more.

The ongoing problem of race in young adult literature (via Amitha Knight)

Speaking of race, the Chronicle of Higher Education published a piece mocking the whole field of Black Studies based on reading the titles of (proposed) dissertations (and a paragraph description). Tressie mc had a trenchant response. The faculty and students also responded.

And segueing from race via race and statistics (and eugenics), most of Galton’s works are now online.

Dirac’s thoughts on math and physics.

A touching film about 9/11 from Eusong Lee from CalArts.

The Early History of the SVD

Posted on by

I recently read G.W. Stewart‘s little paper On the Early History of the Singular Value Decomposition (free tech report version is at UMD). It talks about how Beltrami, Jordan, Sylvester, Schmidt, and Weyl all had different approaches to finding/proving the SVD. It’s worth a quick skim, because goodness knows it appears everywhere under all sorts of names. Part of the problem is characterizing the SVD, and the other is calculating it. Since numerical analysis was never part of my training, I don’t have as much sophisticated appreciation for the algorithmic aspects, but I certainly benefit from having efficient solvers.

One point Stewart makes is that we really shouldn’t call the approximation theorem for the SVD the Eckart-Young Theorem, since Schmidt was really the one who showed it much earlier in the context of “integral equations, one of the hot topics of the first decades of our [the 20th] century.” I’ve been guilty of this in the past, so it’s time for me to make amends. I suppose I better start saying Cauchy-Bunyakovsky-Schwarz too.

What was weird to me is that as an (erstwhile?) signal processor, there was not much mention of the Karhunen–Loève transform, even in the little paragraphs on “principal components.”

Readings

Posted on by

How to Survive in a Science Fictional Universe (Charles Yu) – Not the book you think it is. This was a fantastic read, a meditation on loss and time and memory and connections. Sure there is a time travel, but it’s more about what that means psychologically than technologically. Highly recommended.

Carter Beats The Devil (Glen David Gold) – A fictionalized biography of stage magician Charles Joseph Carter, this is a real page-turner, especially if you like the attention to historical detail. I quite enjoyed it, despite the rather abrupt ending.

Daemonomania (John Crowley) – Book Three of the Aegypt cycle. This one was slow going and hard to get into, but it really picks up in the middle. The costume party towards the end of the book is all worth it, as is the mission to rescue Rosie’s daughter Sam from the cultish Powerhouse. Crowley may be accused of injecting the mystic into the mundane in an artificial way, but I think what this book did was show how desperate circumstances amplify and distort our perceptions to make events seem mysterious or magical.

Tango (Slawomir Mrozek) – a somewhat absurdist allegory about reactionary tendencies. The setting is a rather bohemian family living in a house in disarray, with the father Stromil putting on ridiculous art shows (“experiments”) and ignoring the fact that his wife is cheating on him with a roustabout, Eddie. All of this is very frustrating to Arthur, his son, who longs for a return to the old classical ways. He gets his way by holding them to higher standards at gunpoint, but then realizes the futility of it all. I imagine it’s funnier performed with more dramaturgical context. It takes place between the wars, so that clearly has something to do with it, but my play-reading chops are not up to snuff to say anything insightful.

Complexity and Information (J. F. Traub and A. G. Werschulz) – a gentle, if scattered, introduction to information based complexity, which I had heard about but didn’t really know too much about. It somehow feels “old fashioned” to me (perhaps that’s the machine learning kool-aid speaking), with comparisons to Turing machines and so on. But the central question of how to appropriately estimate integrals from samples is pretty interesting, given my recent forays into using MCMC.

Banach spaces, super-reflexivity, and martingale type

Posted on by

I started reading Convex Games in Banach Spaces, by Sridharan and Tewari and then got interested in the work of G. Pisier on martingales in Banach spaces, which studies how probability and geometry interact. Some of the definitions differ a bit between these papers (the former does things in terms of martingale difference sequences).

A Banach space {\mathcal{B}} has Martingale-type {p} (or M-type {p}) if there is a constant {C} such that for any {T \ge 1} and {\mathcal{B}}-valued martingale {Y_1, Y_2, \ldots}, we have

\displaystyle \sup_{t} \mathop{\mathbb E}\left[ \left\| Y_t \right\| \right] \le C \left( \sum_{t=1}^{\infty} \mathop{\mathbb E}[ \left\| Y_t - Y_{t-1} \right\| ^p ] \right)^{1/p}.

A Banach space {\mathcal{B}} has Martingale-cotype {q} (or M-cotype {q}) if there is a constant {C} such that for any {T \ge 1} and {\mathcal{B}}-valued martingale {Y_1, Y_2, \ldots}, we have

\displaystyle \left( \sum_{t=1}^{\infty} \mathop{\mathbb E}[ \left\| Y_t - Y_{t-1} \right\|^q ] \right)^{1/q} \le C \sup_{t} \mathop{\mathbb E}\left[ \left\| Y_t \right\| \right].

So far these are statements about how martingales behave in these spaces, and you can see a little geometry in the {(\sum (\cdot)^p )^{1/p}} kind of stuff, but how does this relate to overall geometric properties of the space?

A Banach space {\mathcal{B}} is reflexive if it is isomorphic to its double dual (the dual of its dual space). The space {\mathcal{B}} is reflexive if and only if its dual {\mathcal{B}^{\ast}} is reflexive. A space {\mathcal{C}} is finitely representable in {\mathcal{B}} if for any {x \in \mathcal{C}} and any {\lambda > 1} there exists an isomorphism {\phi : \mathcal{C} \rightarrow \mathcal{B}} such that

\displaystyle \lambda^{-1} \|x\| \le \|\phi(x)\| \le \lambda{x}

A Banach space {\mathcal{B}} is super-reflexive if no non-reflexive Banach space is finitely representable in {\mathcal{B}}. A result of James shows that a space is super-reflexive if and only if its dual is super-reflexive. Reflexivity means a space is “nice” and super-reflexivity is a kind of “uniform niceness.”

The norm for a Banach space is uniformly convex if for every {\epsilon > 0} there exists a {\delta > 0} such that for two unit vectors {x} and {y},

\displaystyle \|x + y\| > 2 - \delta

implies

\displaystyle \|x - y\| < \epsilon.

For example, for {p > 1} the spaces {L_p} and {\ell_p} are uniformly convex. Another way to picture it is that if the midpoint of the chord between {x} and {y} is close to the surface of the unit ball, then the chord has to be short. Per Enflo showed that if a Banach space {\mathcal{B}} is super-reflexive, it has an equivalent norm which is uniformly convex.

It turns out that the M-type is related to the degree of convexity of a space, namely how uniformly convex the norm is (and in turn connected to super-reflexivity). A space is {q}–uniformly convex if

\displaystyle \left\| \frac{x + y}{2} \right\|^q \le \frac{1}{2} \left( \|x\|^q + \|y\|^q \right) - C^{-q} \left\| \frac{x - y}{2} \right\|^q.

Gilles Pisier made the connection to M-types : a Banach space is super-reflexive if and only if it has M-type {p > 1} (or M-cotype {q < \infty}). Furthermore, a Banach space has M-cotype {q} if and only if {\mathcal{B}} has a {q}-uniformly convex norm.

So the big picture is this: super-reflexivity is enough to guarantee a uniformly convex norm, but the M-cotype characterizes the degree of how convex that norm is.

References:

Sridharan, Kartik and Tewari, Ambuj, Convex Games in Banach Spaces, Proceedings of COLT, 2010.

Enflo, Per, Banach spaces which can be given an equivalent uniformly convex norm, Israel Journal of Mathematics 13 (1972), 281-288.

James, Robert C., Super-reflexive Banach spaces., Canadian Journal of Mathematics 24 (1972), 896Ð904.

Pisier, Gilles, Probabilistic Methods in the Geometry of Banach spaces, in G. Letta and M. Pratelli, ed., Probability and Analysis, v.1206 of Lecture Notes in Mathematics, p167–241, Springer, 1986.

Pisier, Gilles, Martingales with values in uniformly convex spaces, Israel Journal of Mathematics 20 (1975), no. 3-4, 326Ð350.

Pisier, Gilles, Martingales in Banach Spaces (in connection with Type and Cotype), IHP Winter Course online lecture notes, 2011.

Lovaglia, A. R., Locally uniformly convex Banach spaces, Trans. Amer. Math. Soc. 78, (1955). 225Ð238.

Readings

Posted on by

Shing-Tung Yau and Steve Nadis, The Shape of Inner Space — This book was about the Calabi conjecture, Calabi-Yau manifolds, string theory, and all that jazz. It’s supposed to be for a general/lay audience, but I found it rather daunting and often confusing. Perhaps I know just enough math to get confused, whereas other readers might gloss over things. I definitely would not recommend it to those without some serious mathematical background (like a few college classes). That being said, I found it pretty interesting, and now I know (kind of) what a Calabi-Yau space is.

Donald G. Saari, Decisions and Elections : Explaining the Unexpected — This sums up a large chunk of the analysis of social choice problems and voting systems done by Donald Saari. It’s a bit overwritten for my taste and veers between some mathematical formalism and a chatty form of argumentation. I don’t think I fit in the right “audience” for this book, which is part of the problem. It discusses Arrow’s Theorem and Sen’s Theorem via a bunch of examples and spends a fair bit of time on the “paradoxes” and perversities of different choice systems. The chattiness makes it feel less than systematic. Towards the end Saari puts on more of an advocate hat and argues that symmetry (in a particular sense) is a desirable property of election systems and puts out a case for the Borda count. That in a sense is the least convincing part of the book. This might be a good present for a precocious high school student, since the math is not so complicated but there are a lot of ideas to chew on in there.

Hannu Nurmi, Voting Procedures under Uncertainty — This also fits into the “slightly math-y books for political scientists” genre, so I found it insufficiently math-y. It’s a survey of different models of uncertainty in voting procedures and a survey of the work in that area. As such, it discusses alternatives to “traditional” social choice theory including Euclidean models of preference and so on. There’s a little more “survey” and less “integrating the different perspectives” but that’s ok. I am not sure who should read it, but it did point out some new literatures of which I had previously been unaware.

Moez Draif and Laurent Massoulié, Epidemics and Rumors in Complex Networks — A nice and compact introduction to rumor-spreading processes, including branching processes, small world graphs, SIS/SIR type models, and concluding with some models for “viral marketing.” I really liked this book because it was concise and to the point, but others may find that it lacks some context and connections to literature with which they are familiar. It doesn’t feel like a tutorial in that respect, but it’s self-contained and great for someone who has seen some of the material before but not all of it.

John Mortimer, Rumpole and the Primrose Path — Reading Rumpole short stories is kind of like relaxing in a pair of old slippers. Enjoyable, but probably not his best work.

Readings

Posted on by

The Gangster We Are All Looking For (lê thi diem thúy) — This is a fragmented and short narrative of a young Vietnamese immigrant to the US and her time growing up in various neighborhoods in San Diego. It’s the KPBS One Book, One San Diego selection so there were 25 copies at the library. The little vignettes are fleeting but touching, but in a sense you don’t feel that the narrator is particularly introspective, at least not in a direct way. However, I think it was definitely worth reading, if for no other reason than to hear her unique perspective.

The Terrible Privacy of Maxwell Sim (Jonathan Coe) — A satirical novel which came recommended but which in the end I felt cheated by. Maxwell Sim embarks on a new job after a recent divorce and few months off for depression, and ends up learning new things about himself and his family. He’s a bit of a loser, to be honest, but in the end you kind of feel for him as he muddles through emails, old letters, facebook, and the like. What is a big cheat is the ending, in which the author (!) appears. Blech.

Symmetry and Its Discontents (Sheridan Zabell) — A lovely collection of essays on the philosophy, history, and mathematics of symmetry assumptions in problems of induction. The last two chapters are especially good as they discuss a bit of the history and background of such things as Good-Turing estimators and exchangeable partition processes. I learned about this book a while ago from Susan Holmes at the AIM Workshop on estimating probability distributions.

Electronic Elections (R. Michael Alvarez and Thad E. Hall) — A short but dense book that makes the case for a “risk management” approach to assessing the value of electronic voting machines. Electronic voting machines have all sorts of benefits, including better accessibility for the disabled, no “hanging chads,” and so on. But they are also woefully unsecure and hackable, as has been demonstrated time and again by computer security folks. Alvarez and Hall feel like the CS folks are being unfair and think (in a very nebulous way) that the benefits outweigh the risks. I found the data about voter confusion and error rates, etc. interesting, but I think the authors completely miss the point of the security community’s critique of electronic voting systems. Designing a shoddy electronic voting system is bad, regardless of the purported benefits.