## Truncated SVD … how?

This question has been bothering me off and on for several months now: how *exactly* is the truncated SVD computed, and what is the cost? I’ve gathered that most methods are based on Krylov subspaces, and that implicitly restarted Arnoldi processes seem to be the most popular proposal … in what miniscule amount of literature … Continue reading Truncated SVD … how?

## QOTD: total unimodularity

I started reading Matousek’s discrete geometry book. Specifically, chapter 12 on applications of high-dimensional polytopes. Mostly because he apparently draws a connection between graphs and the Brunn-Minkowski theory, and I’m interested to see exactly what that connection is and if it has any interesting implications. I just finished the proof of the weak perfect graph … Continue reading QOTD: total unimodularity

## My Android ebook reading workflow (optimized for frequent turnover of ebooks)

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 … Continue reading My Android ebook reading workflow (optimized for frequent turnover of ebooks)

## Symmetrized products of positive matrices are not positive

.. 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 … Continue reading Symmetrized products of positive matrices are not positive

## QOTD (from an old IMO): show that none of these sums are integers

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 … Continue reading QOTD (from an old IMO): show that none of these sums are integers

## Reading List for Feb and March 2012

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 … Continue reading Reading List for Feb and March 2012

## Norms of sums of random vectors sampled without replacement

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, \[ … Continue reading Norms of sums of random vectors sampled without replacement