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?
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
Let \(\mat{P}_{\mathcal{U}}\) denote the projection unto a \(k\)-dimensional subspace of \(\C^{n}.\) We say \(\mathcal{U}\) is \(\mu\)-coherent if \((\mat{P}_{\mathcal{U}})_{ii} \leq \mu \frac{k}{n} \) for all \(i = 1, \ldots, n.\) Let \(\mat{A} \in \C^{n \times n} \) be a SPSD matrix whose top \(k\)-dimensional invariant subspace is \(\mu\)-coherent. Given \(\delta > 0\) and \(\mat{S} \in \C^{n \times … Continue reading Are there perturbations that preserve incoherence and give nicely conditioned “submatrices”?
I had a dozen eggs in the fridge that I need to use up by Wednesday; now I’m down to four. I made Jaffa cakes last week (not bad, but not memorable, and definitely not worth the effort: my main complaint is that the cake portion is bland and has a too-tough texture) and I … Continue reading I discover vegetables taste good in Dijon sauce then proceed to spread the gospel
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 … Continue reading Puzzled by the definition of stationarity
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)
.. 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
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
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
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