# Turtle Soup

Some write-downable thoughts about infinity, noise and entropy – by Sushil Subramanian

## Saying Hello in the United States

As a part of my interests in languages, this is the outcome of a small research project. Below is a list of indigenous languages and the phrase “hello” in them, that belonged to Native American peoples that occupied areas in and around the present 50 most populous cities in the United States.

The motivation to do this study arises from a simple, but profound statistic:

Of the 175 Native languages that survived the 20th century, only 55 are spoken by 10 individuals or more. This discounts the fact that at the time of European contact, the number of languages spoken in California alone was 80 of which none remain in the present day. Navajo is the only Native language with more than 100,000 speakers [cite: Wade Davis, Light at the Edge of the World, Feb. 2007].

The choice of the 50 most populous cities will hardly cover the vast reaches of North America that the Natives once used to occupy. However, due to the technology and consumerism driven diaspora of the United States, 79% of the current population is urban and is likely to stay or visit in and around these cities [cite: U.S. Department of Transportation, Census 2000 Population Statistics, May 2011].

Furthermore, the U.S. Immigration and Nationality Act of 1965, made a critical and progressive decision to not limit immigration based on Western European ethnicity, but rather based primarily on the immigrant skills [cite: Wikipedia]. If immigrant skills are an incentive, it is highly probable that most post-1965 modern immigrants live in and around urban incorporated areas, with a large population. For example, as a part of my visit to the United States to pursue my PhD., I have primarily stayed in Los Angeles, the second-most populous city in the United States.

Given these factors, I am optimistic that anyone who reads this list and who currently is in, or wants to visit the United States, will most likely immediately know how to say “Hello” in a language which ran through local peoples’ bloods 500 years ago as much as English for instance, run’s in ours today. Of these individuals, some may be inspired to study these languages further, or be inspired to pursue learning their own native language, at which point, the purpose of this article can be considered fulfilled.

This list was compiled in a very simple manner, following mostly three steps:

1. Obtain a List of U.S. cities by population: Wikipedia is an excellent source.
2. Read the indigenous history of the place and obtain the name of the languages used in the area from Wikipedia or other sources.
3. Use Jennifer Runner’s excellent compilation or other sources as a cross-reference and to obtain phrases.

Using only free resources available on the internet and electronic academic material available for students from the University of Southern California Libraries, details for each city in the list took on average, about 15 minutes to compile. I have tried to make the list as accurate as possible, however, I will be grateful for any mistakes pointed out.

Language loss is one of the greatest threats to the progress of human knowledge. When a language no longer has speakers, a unique wealth of information, inferences and intuitions passed through ages are lost; a flame in the human spirit is extinguished. Languages evolve with time giving rise to new ones, but in the present world, due to the pressures of political power, and the assimilation of peoples with few conscious choices, they are becoming extinct with little chance to naturally develop and flourish.

There are many ways to know about the world’s languages; a simple search on the internet can tell a lot. For example, a project that is particularly interesting and well organized is the Endangered Languages Project.

Written by sushilsub

April 14, 2013 at 11:05 pm

Posted in Blog Entries

## Compressed Sensing: Transmit Nothing – Receive Everything

(I wrote this article on request from my friend Ved Deshpande, for the Mathematics Department, IIT Kharagpur, newsletter, Xponent, as a guest article. There may be some technical mistakes in this article, however, this is how I understood compressed sensing.)

What we know:

In the last 5 years, the discipline of Applied Mathematics, particularly in Communications and Signal Processing has seen a spectacular shift in paradigm. In Sping 2004, David Donoho’s (Stanford) former PhD. student, Emmanuel Candes (presently at CalTech.) first discussed the idea of compressed sensing. From these meetings germinated a novel and phenomenal method of sensing and estimating signals, which Donoho developed. Simultaneously, with the help of post doctoral student Justin Romberg (now at GeorgiaTech.) and Field’s Medalist Terence Tao (UCLA), Candes also nurtured the same idea, which developed into a unique set of papers on compressed sensing. This article is an attempt to expose the beauty of their findings, which often go unnoticed in mathematics and applied sciences.

Consider a digital signal $x(n)$ where  $1 \leq n \leq N$   i.e., the signal has restricted length. In the 1930’s, work done by Shannon, Whittaker and Nyquist suggests that the above signal can be reconstructed with zero-error, if it had at least  $2N$ samples to begin with. This is equivalent to saying, that if  can be represented as a unique linear combination of  unique functions (often called a basis), then a matrix of dimension  $2N \times N$ has to sample the signal for perfectly obtaining the original basis. Since the basis in consideration and the signal $x$ are related by a unique linear combination, if the basis is obtained perfectly,  $x$ can simply be obtained by the relation  $x = \psi \theta \mathrm{,}$ where  $\theta$ is the basis of length $N$ and  $\psi$ is a unique, invertible  $N \times N$ matrix called the transform matrix. For example, some of us may be familiar with the Fourier basis, where $\psi$ is full of  $e^{2\pi j n k / N}$ terms, where $n$ and $k$ are the matrix indices.

Let us think of the entire problem in a different way. Let’s say we want to reproduce the signal most of the times. This means, if we try to reconstruct the signal infinite times in infinite different experiments, we will converge to a probability of reconstruction,  $P$. If we can make $P$ high enough, we can think of posing relaxations on other constraints in the problem. What will be truly interesting is we could manage to get away with sampling the signal with a matrix of dimension $K \times N$ where $K$ is allowed to be lesser than $N$. A bold statement saying that it is indeed possible, in the form of a big blow to the age old theory of Shannon, was declared by Candes and Donoho in their groundbreaking papers in 2004. On the downside however, this works for a specific set of signals only known as sparse signals. In a nutshell, Candes and Donoho said that if the basis is sparse, i.e. it contains very few non-zero elements, then it is possible to sample the signal with a matrix of size $K \times N$ often called a matrix of transformation to a lesser rank, and still manage to get back $x$.

Suppose, the basis $\theta$ is $S-\mathrm{sparse}$ i.e. $S$ out of the $N$ elements of the basis are non-zero. Now we use a $K \times N$ matrix for sampling. Thus the resulting signal is of length $K$ which can be represented as $y = \phi x = \phi \psi \theta$. This signal has been proven to be enough to get back $\theta$. Amazingly, Candes and Donoho also showed that as long as $\psi$ and $\phi$ are highly incoherent (a mathematical formulation of how unrelated the matrices are), $\phi$ can be completely random! Further, $K$ can be as less as $S \log N$ and the probability of failure $\left(1-P \right)$ is about $e^{-1/N}$. If $S = 3$ and $N = 100$ it implies $K \approx 14$ which is way lesser than that predicted by Shannon! At first it may seem that $y$ being a $K-\mathrm{length}$ vector means that to obtain $\theta$ we actually have more variables than equations (if $\phi$ and $\psi$ are assumed known). However, this problem is cleverly overcome by Candes and Donoho using the concepts of linear programming and convex optimization often used in electrical engineering and operations research.

The Implications:

Compressed sensing (aptly termed, as we compress the way we measure or “sense” as mentioned above) has far reaching implications in the applied sciences and engineering fields. One application is in underwater communications. In underwater communication channels, signals are usually distorted by a channel response which can be modeled as a sparse signal, very similar to the basis described above. The transmitted signal convolves as a matrix similar to $\psi$, and the signal is then available to a receiver. Now that we know that the channel response is sparse, we can measure the signal to obtain a $K-\mathrm{length}$ signal that can perfectly give us back the channel response! This channel response comes in very handy in finally removing the Gaussian noise from the data. Thus, in effect, we are measuring a signal as if nearly nothing has been transmitted and every required information is available!

The DSP Lab at Rice University have archived and update all the latest literature on compressed sensing. Visit them at: http://www.dsp.ece.rice.edu/cs/.

Written by sushilsub

May 16, 2009 at 2:59 pm

Posted in Blog Entries

Tagged with ,