Category: Uncategorized

I’m reading Santosh Vempala’s survey “Geometric Random Walks: A Survey,” and already I’m puzzled at one of the very first definitions he gives.

Define a Markov chain as a state space sigma algebra pair \((K, \mathcal{A})\) with transition probability measures given by \(P_u\) for each \(u \in K.\)

A distribution \(Q\) on \((K, \mathcal{A})\) is called stationary if one step from it gives the same distribution, i.e., for any \(A \in \mathcal{A},\)
\[
\int_A P_u(A) \, dQ(u) = Q(A).
\]

This definition makes sense in words, but mathematically it doesn’t seem sound: unless \(P_u(A) = 1\) a.e. (with respect to \(u \in A\)), this equality can’t hold. I must be missing something…

Update:
The definition should involve integration over the whole space:

A distribution \(Q\) on \((K, \mathcal{A})\) is called stationary if one step from it gives the same distribution, i.e., for any \(A \in \mathcal{A},\)
\[
\int_K P_u(A) \, dQ(u) = Q(A).
\]

That this is so can be seen from the discrete case. Just goes to show you that you have to be careful even when reading peer-reviewed articles.

Synopsis: Aldiko’s not appropriate if you plan on constantly rotating the collection of ebooks on your mobile device. Instead, a combination of Calibre, Moon+Reader, and DropBox seems to do the trick. Consider using Moon+Reader as your default reader unless you need Aldiko’s capabilities for dealing with large ebook collections, as Moon+Reader has a more polished reading experience than Aldiko.

A major contributor to my decision to get an Android tablet was my desire to be able to read ebooks comfortably. Namely, with more portability and a form factor closer to the usual book experience. (the other major contributor was my desire to be able to read research papers comfortably, but that’s an issue for another discussion)

Until recently I was using Aldiko as my primary ebook reader, because it seems to be most popular reader, going both from the Android Market impression and Google searches for “Android ebook reader” and similar terms. Aldiko’s great if you have a large, static, well-tagged collection of EPUBs. The interface makes it a breeze to find books based on tags or authors, and keeps track of your recent reads, but it has some really annoying drawbacks. First, it is awful at properly removing books: it leaves behind the tag information for files that have been deleted. Even reinstalling Aldiko doesn’t seem to fix this. On a related note, oftentimes Aldiko has multiple index entries for one book. This may have been due to me having two formats of the same file, but one would expect that any ereader should recognize this and adjust accordingly.

These are somewhat major usability issues, but the main problem I have with Aldiko is that it’s just not aimed at a user like me, who constantly switches out ebooks. Aldiko is not designed for rapid turnover of books. It’s aimed more at people who store all their ebooks on the device, add books occasionally, and don’t delete any books. That’s a dealbreaker for me, since I have lots of ebooks, don’t want to waste space on my tablet storing files I won’t look at for several years, and want to regularly switch out books I’ve finished reading for ones I plan on reading soon.

Tonight I’ve been experimenting with a new setup of Calibre, Moon+Reader, and DropBox that seems to provide a setup that suits my style more. Moon+Reader has a book database, just as Aldiko does, but it’s also more amenable to reading EPUBs on a file-by-file basis (I forgot to mention that Aldiko can’t just load an EPUB off the disk: you have to import it into Aldiko’s special purpose database first). I’m quite impressed with the reading experience in Moon+Reader: it doesn’t have the collection organizational tools of Aldiko, but on a per-book basis, the navigation capabilities and formatting options as well as the overall feel of the application is more polished.

My setup is simple: in Calibre, I use the “connect to folder” option to load my DropBox folder as a device, then sync the books I’m currently reading to the device. On my tablet, I then open the files from DropBox using Moon+Reader. As long as I don’t reboot the tablet (or force kill DropBox), I’m able to interact with the file as though it were stored permanently on the tablet (e.g. Moon+Reader will store your location and return to it every time you visit the book). If you want, you can also favorite the ebook files in DropBox so that a local permanent copy of them is mirrored to your tablet, and then import them (from your DropBox scratch folder) into Moon+Reader. This method has the advantage that you don’t lose any metadata when you reboot the tablet, and if you delete the files from DropBox, they’re deleted locally and automagically from Moon+Reader. The only disadvantage to this technique is that the DropBox application doesn’t let you favorite folders for now, so if you have multiple ebooks in a folder, you have to favorite them all manually. This isn’t a big deal.

.. duh. This is in relation to the symmetrized matrix AM-GM inequality conjectured by Recht and Re. The most obvious/direct way of maybe attempting to prove this inequality is to show the semidefinite inequality
\[
\left(\frac{1}{n}\sum\nolimits_{i=1}^n\mat{A}_i\right)^n \succeq \frac{1}{n!} \sum_\sigma \mat{A}_{\sigma(1)}\mat{A}_{\sigma(2)}\times\cdots\times \mat{A}_{\sigma(n)}.
\]

Unfortunately, the right hand side isn’t even a positive matrix in general. The proof is pretty ridiculously simple, but I console myself with the fact that it wasn’t immediately obvious to some folks I’ve discussed this problem with that the symmetrized sum on the rhs could be nonpositive in general.

Consider the case of just two summands. Then \(\vec{x}^T (\mat{B}\mat{A} + \mat{A}\mat{B}) \vec{x} = 2\vec{x}^t \mat{B}\mat{A} \vec{x},\) so \(\mat{A}\mat{B} + \mat{B}\mat{A}\) is positive only if \(\mat{A}\mat{B}\) is positive. This in turn implies \(\mat{A} \mat{B} = \mat{B}\mat{A},\) so at least in this case, the matrices must commute for the symmetrized sum to be positive.

Here’s an old IMO question (or maybe it’s off one of the short or long lists) that I haven’t made any progress on:

Show that for any natural numbers \(a\) and \(n\) the sum
\[
1 + \frac{1}{1+a} + \frac{1}{1 + 2a} + \cdots + \frac{1}{1+n a}
\]
is not an integer.

An obvious and cool corollary is that the harmonic numbers are never integers.

My top picks, with links if you want to tag along:

• Ledoux and Talagrand (available from Talagrand’s webpage). Specifically, the chapters on Rademacher and Gaussian sums, symmetrization and contraction properties, and tail bounds for sums of random vectors. Also the bits on scalar martingale arguments.
• Sourav Chatterjee’s thesis and its matrix counterpart. He came up with a beautiful approach for deriving concentration inequalities from exchangeable pairs which generalizes nicely to the matrix case.
• Plan and Vershynin’s works on one-bit compressed sensing, tessellation for dimension reduction, and sparse logistic regression. I’ve said it before and I’ll say it again: I’m not interested in compressed sensing per se. But the concentration and geometric techniques they use are both beautiful and useful, and I’m interesting in learning them.
• Robust computation of linear models, or How to find a needle in a haystack. Robust PCA is more interesting than compressed sensing, but again I’m most interested in the tools here.
• Candes et al.’s paper on subspace clustering. Interesting problem and interesting geometric tools.

Let \(\mathbb{P}_{WOR(\ell)}\) denote a probability under the model where a set \(I\) of \(\ell\) indices is sampled without replacement from \(\{1,2,\ldots,n\}\), and \(\mathbb{P}_{WR(\ell)}\) denote a probability under the model where the \(\ell\) indices are chosen with replacement. Then is it the case that, for any collection \(\vec{v}_i\) of \(n\) vectors in a vector space,
\[
\mathbb{P}_{WOR(\ell)}\left(\left\| \sum\nolimits_{i \in I} \vec{v}_i \right\| \geq t \right) \leq \mathbb{P}_{WR(\ell)}\left(\left\| \sum\nolimits_{i \in I} \vec{v}_i \right\| \geq t \right)
\]
up to constants?
In general, the \(WOR(\ell)\) model is harder to work with, because the terms in the resulting sum are dependent, whereas the terms in the \(WR(\ell)\) sum are independent. So if this inequality held, it would make life easier.

I don’t know if this inequality is true in general, but there are classical exponential tail bounds for the rhs, and I believe that those bounds hold up to constants for the lhs. Here’s an outline of the argument. The key fact is that
\[
\E_{WOR(\ell)}f\left(\sum\nolimits_{i \in I} \vec{v}_i\right) \leq \E_{WR(\ell)}f\left(\sum\nolimits_{i \in I} \vec{v}_i\right)
\]
for any convex function \(f.\) This was originally realized by Hoeffding, but Gross provides a more readable account. Take \(f(x) = \exp(\|x\|)\) to see that the moment generating function under the \(WOR(\ell)\) model is dominated by the moment generating function under the \(WR(\ell)\) model.

Next step. We know that the deviation of the norm of the sum from its expectation under the \(WR(\ell)\) model satisfies a Bennett inequality (see Ledoux and Talagrand, chapter 6):
\[
\mathbb{P}_{WR(\ell)}\left( \left|\left\|\sum\nolimits_{i \in I} \vec{v}_i\right\| – \E_{WR(\ell)} \left\|\sum\nolimits_{i \in I} \vec{v}_i \right\| \right| \geq t \right) \leq \exp\left[\frac{t}{2a} – \left(\frac{t}{2a} + \frac{b^2}{4a^2} \right) \log\left(1 + \frac{2 a t}{b^2} \right) \right].
\]
Here \(a\) is a bound on the norms of the individual summands and \(b^2 = \ell/n \cdot \sum_{i=1}^n \|\vec{v}_i\|^2.\)
From the tail bound/moment/mgf connection, we know that from this tail bound we can recover a bound on the mgf of this deviation under the \(WR(\ell)\) model that allows recovery of the Bennett inequality from the usual Chernoff arguments (up to changes in the constants).

(Alternatively, I realized latterly, you can just look for a proof this or a similar inequality which proceeds by bounding the mgf, and use that bound directly rather than reverse engineering to get a similar but looser bound. The issue here is that you have to find a proof of this inequality with uses the mgf. I was not able to do this, but I didn’t try too hard, and there are similar results in chapter 1 of Ledoux and Talagrand which are good enough for my purposes)

Now we do some algebra to bound an mgf involving the norm of the sum formed under the \(WOR(\ell)\) model:
\[
\E_{WOR(\ell)} \exp\left(\lambda \left\|\sum\nolimits_{i \in I} \vec{v}_i \right\|\right) \leq \E_{WR(\ell)} \exp\left(\lambda \left\|\sum\nolimits_{i \in I} \vec{v}_i \right\|\right)
\]
from our first observation, and the right hand side is smaller than
\[
\E_{WR(\ell)} \exp\left(\lambda \bigg|\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\| – \E_{WR(\ell)}\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\|\bigg| \right) \exp\left(\lambda \E_{WR(\ell)}\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\|\right),
\]
so rearranging gives
\[
\E_{WOR(\ell)} \exp\left(\lambda \left[\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\| – \E_{WR(\ell)}\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\|\right] \right) \leq \E_{WR(\ell)} \exp\left(\lambda \bigg|\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\| – \E_{WR(\ell)}\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\|\bigg| \right).
\]

Recall that we have a bound on the rhs from the Bennett inequality. Thus we have a bound on the mgf of the deviation of the norm of the sum under the \(WOR(\ell)\) model above the expectation of the norm of the sum under the \(WR(\ell)\) model, and this bound is sufficiently strong to generate a Bennett inequality. Thus, caveat! up to changes in the constants (since I have not done the calculations), we have that
\[
\mathbb{P}_{WOR(\ell)}\left(\left\| \sum\nolimits_{i \in I} \vec{v}_i \right\| \geq t + \E_{WR(\ell)}\left\|\sum\nolimits_{i \in I} \vec{v}_i \right\| \right) \leq \exp\left[\frac{t}{2a} – \left(\frac{t}{2a} + \frac{b^2}{4a^2} \right) \log\left(1 + \frac{2 a t}{b^2} \right) \right].
\]

Wooo woooo! I just found George Gently‘s coming (came?) back for 2011. I also found out that there was a 2010 season! Too bad Netflix doesn’t have it yet 🙁

Here’s the first Netflix review I (remember having) ever wrote. I was that impressed by the show. Hope I can share that enthusiasm. For some reason Netflix removed all the apostrophes in the review.

George Gently’s an older DI at the Yard who thought he was ready to retire after his wife was murdered because of his crusade against corruption in the force, but a fresh lead on the trail of the man he suspects is behind the murder of his wife brings him back into the game, this time in Northumberland. He’s assisted in his investigation by John Bacchus, a young, ambitious, and brash inspector who, from past bitter experience, Gently sees exhibits all the earmarks of becoming corrupt. So, after the case is resolved, Gently decides to stay on in Northumberland and take the youngster in hand. Thus the first episode sets the stage … after that, each episode deals with a new case.

Yes, the cases are interesting, and the setting is verisimilar, but the appeal of the series for me lies first and foremost in the relationship between Gently and Bacchus. Bacchus is, from the beginning, an unsympathetic character: for no readily apparent reason, he’s unsatisfied with his marriage, and perhaps unconsciously sabotaging it; he’s willing to do whatever it takes — beatings, planting evidence, accepting bribes — to close a case; and his general opinions on race and gender issues reflect those of the times in an unflattering manner. Yet, you can’t help but get the feeling that there’s something salvageable under those youthful excesses. Gently does an excellent job of mentoring Bacchus in a show-and-not-tell manner, but it’s unclear if Bacchus is taking in the messages Gently’s trying to get across or if he’s simply humoring him.

The two episodes of season three are the best of the series. In the first, Bacchus and Gently come to loggerheads over a case involving a child, and in the second, we see concrete hints that Bacchus is becoming a better man. I’d love to see more in this series, but this was a great stopping point. Always leave them wanting more, right?

Looks like I’ll be visiting U. Michigan for a week or so at the end of October. What does one do on such a visit? I’ve been invited to give a talk, but that doesn’t occupy more than an afternoon…

I spent this morning reading through some of the literature on subspace tracking, then wound up visiting Nocedal and Wright for a refresher on the augmented Lagrangian method (Chap 17). Flipping through the book, I came across the following question:

Show that every point on the unit circle is a limit point of the sequence
\[
\vec{x}_k = \left(1 + \frac{1}{2^k}\right) \begin{pmatrix} \cos k \\ \sin k \end{pmatrix}.
\]

Not challenging (esp. if you don’t go into the nasty \(\varepsilon-\delta\) details ), but it’s a cute problem.

Because a picture’s worth a thousand words:

The matrix involved is a projection, not some numerically unstable thing like the Hilbert matrix. You suck at linear algebra, Mathematica.