Often we need a to write a program that iterates over all combinations of \(k\) elements from some set (elements chosen without replacement). It isn't obvious how to efficiently traverse through all these sets, although if bitwise arithmetic is readily available one can use Gosper's Hack. This kind of problem …

## Articles by Christian Chapman

## If M's components are only known up to a factor of (1±ε) then what is det(M)?

Say \(M\) is an \(n\times n\) complex matrix and we would like to learn its determinant. We observe another matrix \(\hat{M}\) whose components are each within some factor of \(M\), in other words \(\hat{M}_{ij}=c_{ij}\cdot M_{ij}\) and each \(c_{ij}\in (1- …

## Some Interaction Information Examples

Interaction information between three random variables has a much less immediate interpretation compared to other information quantities. This makes it more tricky to work with. An i.i. term \(I(X;Y;Z)\) between \(X,\ Y\) and \(Z\), could be either negative:

If we are trying to specify \(X\) with …

## Porting PostmarketOS to the Motorola Photon Q

PostmarketOS has a goal to make old cell phones useful past their shelf life. Right now their efforts are towards getting Alpine Linux to run on as many phones as possible. The majority their codebase right now is a tool called

`pmbootstrap`

that automates parts of porting Alpine. Porting is …## Point KL-Divergence is not Very Negative Very Often

If \(X\sim P\) then for any distribution \(Q\) it is unlikely that \(Q\) ascribes much greater density to \(X\)'s outcome than \(P\) does. In fact if \(P,Q\) have PDFs \(f_P, f_Q\), then:

\begin{align} \mathbb{P}(f_P(X)\leq c f_Q(X)) &= \int \mathbf{1}_{\{x …## Tails of Probability Distributions are Nowhere Dense

Lately I have been thinking about Kullback-Liebler divergence on probability distributions, also called the KL discriminant or relative entropy. It is often useful to think about this quantity as a distance, even though it doesn't behave much like one: it's not symmetric, it doesn't follow the triangle inequality, and even …

## Thoughts on Demosaicing for X-Trans Sensors

A lot of new Fujifilm cameras use their own brand of 'X-Trans' sensors which have a non-Bayer color mosaic. Fujifilm claims that the less regular arrangement makes it more uncommon for edges in the scene to make moire patterns with the mosaic. They say this justifies not including an optical …

## Update: Extracting Information from Noisy Observations

This is meant as a follow-up for the last post's motivation. In summary we have a bipartite graph \(G=(U,V,E)\) with bi-adjacency matrix \(A\) and with \(|U|\approx rk,\) \(|V| \approx ck,\) \(|E|\approx rck,\) \(\mathsf{deg}(u)\approx c,\) \(\mathsf{deg}(v)\approx r,\) and a sequence …

## Thoughts about Extracting Information from Sequences of Noisy Observations

Often we have some quantity of interest that we can only observe indirectly. In these situations, we would like to know how much relevant information we can extract from our noisy, indirect observations, and how to perform the extraction. Figuring out how to do this would in theory allow you …