Sushil Subramanian – Weblog

Essays on engineering, music, culture and their curious intersections – by Sushil Subramanian

USC ANTH 372, Part 1: The Inca Pilgrimage to the Shrine of Taytacha Qoyllur Rit’i

leave a comment »

(This is Part 1 of a series of articles concerning “ANTH 372: Interpretation of Myth and Narrative”, a course I took at USC in Fall 2014. This essay is a short paper we were asked to submit, that analyzes the relationships between myth and ritual, using a case study.)

The festival of Qoyllur Rit’i is an annual Inca pilgrimage that occurs around during the time of Corpus Christi, in late May or early June. The festival attracts several pilgrims, mostly from the peasant communities of villages surrounding Cusco, the ancient capital of the Incas [1]. The pilgrimage consists of several journeys undertaken by the population to the shrine of Lord Qoyllur Ri’ti and of Virgen de Fatima, located at the mountains of Colquepunku and Sinakara in the regions close to Cusco.

The rituals involved in the festival have a distinct pagan atmosphere, and draws interest especially from academics, due to its simultaneous sponsorship by the Catholic Church [3]. Being the largest indigenous pilgrimage of the western hemisphere¹, understanding Qoyllur Rit’i gives several insights into Andean culture and how Catholic flavours are applied to a pre-Columbian ritual, thus creating a relevant phenomenon in the modern Americas.

This short paper briefly states the official Catholic mythology and the pre-Columbian origins of the festival. We also devote a section to understanding the ritual and the inherent dualism and structure in Andean society and culture. Some modern and alternate interpretations of the rituals are mentioned in Section 4, after which, we conclude with an examination of the future of the festival.

1: History and Catholic Officiation

The official Catholic version of the story of Lord Qoyllur Rit’i (Quechua: Taytacha Qoyllur Rit’i), from the church records of Ocongate, is as follows [2]. In 1780, an Indian boy named Mariano Mayta used to watch over his father’s herd of llamas and alpacas on the slopes of the mountain Colquepunku. One day, to escape his brother’s bullying, he wandered into the snowfields of the mountain, where he found a mestizo boy, called Manuel. They became good friends and Manuel provided Mariano with food so that he did not have to return home for provisions. When Mariano’s father found out, he went looking for his son and was surprised to find his herd had miraculously increased. As a reward, he sent Mariano to Cusco to get new clothes. The boy asked permission to buy some for Manuel as his friend wore the same outfit everyday. His father agreed, so Mariano asked Manuel for a sample of his clothes to buy the same kind of material in Cusco.

Upon examination at Cusco, the sample turned out be a fine canonical cloth. When the matter reached the ears of the bishop of Cusco, he ordered an expedition to inquire the sacrilege. On June 12, 1783, the commission ascended Colquepunku with Mariano and found Manuel near a rock, shining with a bright light. Blinded, they retreated only to come back later with a larger party, on June 23, 1783. In their second try they were able to reach Manuel despite the intense light. However, on touching him, he became a tayanka bush (Baccharis odorata) with the body of an agonizing Christ hanging from it. Mariano, thinking they had harmed his friend, fell dead on the spot. He was buried under the rock where Manuel had last appeared.

The tayanka tree was sent to Spain, requested by King Charles III. As it was never returned, the natives of Ocongate protested, forcing the local priest to order a replica, which became known as Lord of Tayankani (Quechua: Taytacha Tayakani). However, the rock under which Mariano was said to be buried attracted a great number of Indian devotees. Religious authorities ordered the painting of an image of a crucified Christ on the rock. This image became known as Lord Qoyllur Rit’i (Quechua for “Lord of Star Snow”).  To this day, the replica image of Lord Tayankani is kept in Ocongate, and the image of Lord Qoyllur Rit’i is taken back to Mawallani.

The key point in the above narrative is, that while Catholics saw Christ in Manuel, the natives placed emphasis on the rock [2]. We thereby obtain some hints, even from the veiled Catholic versions of the story, that the festival could have a pre-Columbian significance, as rock, snow and the geography in general was sacred to the Andes and played critical roles in the Andean cosmology [7].

To a large extent the Catholic myth is very similar to several myths of Latin America, and especially the Andes. They involve the isolation of a peasant, usually on top of hill, eventually resulting in the sighting of Christ or the Virgin [3]. An example, is the San Juan Diego myth that resulted in the holiest of sites in Latin America, Our Lady of Guadalupe in Mexico City [1]. The commonalities suggest that all such Catholic myths may have a more indigenous background.

A few months before he discovered the famed Ice Maiden in 1995, Johan Reinhard explored the region near Colquepunku only to discover several Andean structures that were temporary resting areas offering a well-lit panoramic view for pilgrims approaching the mountain [6]. These, of course, were abandoned after the Spanish conquest, and the processions now approach the mountain from the shadows, suggesting that early Spanish-era natives avoided the watchful eyes of their colonists, so that a pre-Columbian ritual may continue.

The history of the Andes offers more insight into the official version. In 1780, the Tupac Amaru (claiming to be a descendant of the last Inca king) rebellion of the natives against the loyalists to the crown, was primarily motivated by a temporary Andean revival. The severe betrayal resulted in many executions by 1783. Not so surprisingly, the miracle occurred in the same year, a clear indication that the ritual needed to be masked with a Catholic version, to avoid further uprisings [3].

2: A Pre-Columbian Origin

The participants in the ritual that make the trek to Qoyllur Rit’i come primarily from two divisions in the Cusco region, Paucartambo (with a capital of the same name) and Quispicanchis, who have their capital at Ocongate [2]. The two regions are reminiscent of an ethnic divide between the agriculturist Quechua and the merchant Aymara. This has some relation to the Spanish era division of Indian versus Mestizo. Accordingly, the geographies of the two sets of villages come to be separated symbolically as mountain versus valley, highland versus jungle etc., reflecting the geographies of the respective townships.

In the rituals of the pilgrimage, these divides are primarily signaled by the use of dance. Each set of villages sends dancers who have specific functions en route the pilgrimage. Three main dance forms are observed. The first style, the ukuku represents a trickster man-bear whose leads the procession and whose main function is to retrieve the holy water from Lord Qoyllur Rit’i and pass it on to the peasants, who use it for medicinal purposes. The second dancer, is the qhapaq qolla, who is primarily Aymara, representing well-to-do merchants who visit the Quechua. The third are the ch’unchos, representing the uncivilized Indians living in the jungle, who the Incas believed were former (“primitive”) versions of themselves, banished by the Sun God Inti. They are classified variously. All three dances have their own musical repertoire that use different instruments and are deliberately made dissonant and chaotic to each other. The reason for this will be examined in a later section.

The ritual itself involves the pilgrims accumulating on Sinakara and staying overnight for many days. A mass takes place on an evening, after which the divisions Paucartambo and Quispicanchis each lay out their plans to visit the glacier [2]. The next day, the official Catholic myth is recited and the ritual reaches a climax into the evening when the procession, led by the respective ukukus reach the glacier to pay homage to the Taytacha at the dawn of sunlight (they retrieve a cross that had been placed well before). Here, they carve out chunks of the snow, and bring it back to the pilgrims. The shrine of Lord Qoyllur Rit’i is then taken to Ocongate (the entire troupe is usually always dancing throughout the 25 km journey) where it is now handed over and replaced by that of Lord Tayankani [2]. A “pilgrimage within a pilgrimage” takes place at Ocongate, where after a series of dances and recitations, all the dancers who were apparently out of synchronization, suddenly change to a common tune and zigzag each other in a massive spectacle of unison. The shrine of Lord Tayankani is then entered and the festivities begin with markets and feasts being setup in anticipation of Corpus Christi².

There are three questions that are not fully addressed by the official Catholic version [3]. Firstly, why should the festival be held at the time of Corpus Christi. Second, why should the ceremonies be held on the mountains Colquepunku and Sinakara (thereby indicating a pagan association). Finally, why is the rock as important as the Christ that adorns it.

From various sources, it is evident that the celebration honours the arrival of the Pleiades, which appear over Cusco in the beginning of June [3]. The Pleiades were important to the Incas who determined the health of their crops based on their time of arrival. Corpus Christi was also celebrated in the 1600s by the Incas by the name Oncoymita which means ”feast of the Pleiades”. Since Corpus Christi is a moveable holiday around the same time, it fit well into the agriculturist calendar of the Quechuas.

The significance of Colquepunku is related to the Andean concept of apu or the sacred mountain. Apu Colquepunku is one of three (Colquepunku, Qanaqway and Huanucuari) apus that represents the health of people, directly tied to crops and therefore, the Pleiades. The ukuku is a rebellious man-bear that defeats the condenado, a social outcast and criminal that haunts the apu slopes. In doing so, the condenado is delivered and the ukuku is accepted by the community, as it is brave enough to venture into the mountains. Here again, the significance of the apu is readily seen.

The presence of the ch’unchos also suggest a kind of overall civilizing process that occurs during the festival, apart from the general anticipation of health and harvest. The ch’unchos are part of the “old ones” or the naupa machu who were too proud to accept the power of the apus. They were banished at the first dawn of sunlight and cast into stones. However, some escaped into the jungle. Since the shrine is visited at the dawn of light, their presence adds a commemoration of their fights with the apus. The ch’unchos, although less important in comparison to the ukuku and the qhapaq qolla, are usually present in larger numbers with very vivid costumes, representing the moonlight jungle dwellers.

Thirdly, the sacredness of the rock itself is related to the Inca huacas or sacred spots in the geography of the Andes. The Christ of Qoyllur Rit’i and the Virgin Fatima are therefore, attempts to mask Apu Colquepunku and Mama Sinakara.

3: Dualism and Resolution

In Inca mythology, time is divided into world cycles, with each cycle separated from the other by a pachacuti, or the overturning of the world. Within the cycle, there is a binary system of the hanan or “upper” and the hurin or the “lower”. The divisions are relative to themselves; higher elevations are hanan whereas the jungles and lower elevations are hurin. However, the naupa are considered hurin relatively to the dwellers in the mountains, closer to Cusco. On the other hand, from the perspective of the Quechua, the naupa are still hanan compared to the qhapaq qolla, as they originally belong to the mountains, whereas the qhapaq qolla are Aymara, who are physically present in the valleys. Therefore, there is a binary stratification in multiple dimensions, taking hints from both geography and mythology.

The transition between the worlds is represented by a confusion of the hanan and hurin thus resulting in a pachacuti and thereby, a new beginning [3]. The initial dissonance of the various musicians in the pilgrimage, represents the dualism of society; i.e. the ch’unchos and qhapaq qolla being opposed to each other. The confusion that results takes a climax and then resolves in synchrony when all the musicians sing and dance in unison. This represents the pachacuti and the resolution resulting in world order and a new era.

Inca society often consists of various fights and duels called tinkuys [2]. The eventual outcome of these fights is usually sacrifice or exchange of goods and women. While the resolution of the mountain and valley dwellers takes place, simultaneously, the battle between ukuku and condenado both representing beings in a confused state that are either banished for committing pranks and crime respectively, takes place at the apu. The defeat of the condenado in the hands of the ukuku also resolves their confusion (a sort of internal, psychological hanan and hurin within each of them). It is common to see the ukuku being whipped in the procession, in order to prevent his animal nature from offending the site. After the whipping, the ukuku promptly kisses the whip and hugs the whipper, again a resolution.

The ukuku also behave as a mediator between chaos (resulting from the divide) and order (resulting from the resolution). The ukuku a bear-like figure is probably derived from the spectacled bear of the high South American jungles, which is active during dawn. The young man who dances the ukuku speaks with a falsetto thus being a mediator between man and woman. In general the ukuku talks between the community and the apu and the community and the hurin relative to them.

The geographical location of the apu Colquepunku also plays a significant role in the transition from chaos to order. Qoyllur Rit’i lies on the east between the jungle and the snowfields, thus making it an appropriate location for a tinkuy.

4: Modern Interpretations, Further Research

In the early 1500s, a few years before the Spanish invasion, two Inca royal half-brothers, Huascar and Atahualpa fought for the Inca throne, with Huascar being defeated. Since Atahualpa was loyal to the Spanish crown before being executed by them, it is believed that the battle between the two brothers was actually a pachacuti. There is also some evidence that their grandfather, King Topa Inca Yupanqui predicted the arrival of the Spaniards [3]. Atahualpa wished to establish a Viracocha (an apu associated with the end of world cycles) lineage in contradiction with that of Huascar’s Inti lineage. This resulted in killing of all families of the King, and the destruction of a 100 years of ancestral property, thus a pachacuti.

Therefore, it is common to interpret the Spanish arrival as the hurin Spaniards eventually becoming hanan. Since the Spanish did not bother to reinstitute the Viracocha lineage, a new mythology was born, fusing the Viracocha and the Inca, called the Inkarri (Inca + Rey, meaning “king” in Spanish). It is important to see contemporary Andeans in the light of the Viracocha and not the Inti and to this day, Andeans believe in the return of Inkarri.

Qoyllur Rit’i, in the modern sense, is therefore also reinterpreted as a ritual to bring back Viracocha and deliver the Andeans from the perpetual state of chaos, depicted by the disappearance of the Pleiades [3]. A special dance in the ritual, is the Taqi Oncoy or the Dance of the Pleiades, that announces the sighting of the Pleiades. This dance makes no mention of Inti (in spite of the sun being an important part of the Qoyllur Rit’i pilgrimage), thus giving some evidence of the relations to Inkarri.

There have been alternate studies on the pilgrimage. In [4], the author examines the emotional experiences of pilgrims involved in the procession. Often times, pilgrims spend sleepless nights in the cold of the mountains, while performing the various rituals involved [7]. In [5], the author examines miniatures made of pebbles sold and used during the festival as a relation to the ancient Inca script of the kipu, and their abilities to communicate with the apu. Indeed, there still remain many aspects of Qoyllur Rit’i open for understanding and appreciation.

5: Future of Qoyllur Rit’i: Documentation and Relevance

The festivities at Qoyllur Rit’i have undergone several changes in the modern era. Besides technological sophistication of the ritual (i.e. better roads, standardized costumes etc.), there has been a more prominent involvement of the Catholic church; the archbishop of Cusco has in the past blessed the procession, thereby reinforcing Catholic control [2]. Many committees have been formed in recent years to conduct the event in an orderly fashion.

The event has also been a subject of discussion in contemporary issues, for example, cited as being in danger due to global warming and receding glaciers [8]. Several pilgrims note that in earlier days the glacier came down from Sinakara and the procession did not travel that far up the mountains to retrieve the snow [3].

The event is seeing an increasing number of pilgrims every year, and is a subject of documentaries [7]. In conclusion, in spite of hundreds of years of Spanish cultural domination, Qoyllur Rit’i remains an indigenous phenomenon, constantly changing and adapting to the requirements of modern Peru.


¹Although the number of pilgrims has increased from 25000 in 1984 to more than 70000 in recent years, there is no strict statistic to verify the festival as the largest in the western hemisphere. However, several news articles claim so; see for example:

²Further details of the ritual are available in [2], where the author himself admits to brevity. The author also provides some history of the ritual, i.e. certain dangerous, life-threatening aspects have been toned down


[1] V. Revilla, “Qoyllur Rit’i: In search of the lord of the snow star”, Society, Vol. 38, No. 3, pp. 55-59, Mar. 2001.

[2] M.J. Sallnow, “Dual Cosmology and Ethnic Division in an Andean Pilgrimage Cult”, Pilgrimages in Latin America: Contributions to the Study of Anthropology; Greenwood Press, No. 4, pp. 281-306, Feb. 1991.

[3] R. Randall, “Qoyllur Rit’i: An Inca Fiesta of the Pleiades”, Bulletin de l’Institut Francais des Etudes Andines, Vol. 11, No. 1-2, pp. 37-81, 1982.

[4] G.S. Carreño, “The Glacier, the Rock, the Image: Emotional Experience and Semiotic Diversity at the Quylluriti Pilgrimage (Cuzco, Peru)”, Signs and Society, Vol. 2, No. S1, pp. S188-S214, 2014.

[5] C.J. Allen, “When Pebbles Move Mountains: Iconicity and Symbolism in a Quechua Ritual”, Creating Context in Andean Cultures: Oxford Studies in Anthropological Linguistics; Oxford University Press, No. 6, pp. 73-84, Apr. 1997.

[6] J. Reinhard, “The Ice Maiden: Inca Mummies, Mountain Gods, and Sacred Sites in the Andes”, National Geographic Society, Jun. 2006.

[7] A. Gregg and W. Davis, “Light at the Edge of the World: Sacred Geography of the Andes”, National Geographic Channel, 2006.

[8] C. Ceruti, “Sacred Ice Melting Away: Lessons from the impact of climate change on Andean cultural heritage”, The Journal of Sustainability Education, Feb. 2013.

Written by sushilsub

October 17, 2014 at 11:38 am

In the Indies: Music and a Historical Narrative

leave a comment »

(I presented a modified version of this lecture-recital to a group of fellow amateur pianists in Long Beach, California, United States, in February 2014. The video links are integral to the programme and it is suggested that they be watched in sequence while reading the lecture.)

I would like to present to you a different kind of performance today; not classical music, but a lecture followed by a few short traditional pieces.

While studying towards my PhD. in the United States for the past five years, I’ve devoted a significant portion of my spare time into music, particularly of the piano, and reading books on history and culture. Given my interests, and having stayed in a foreign country half way across the globe for nearly a fifth of my life, naturally, I was fascinated to know more about the history and culture of this land.

Three years ago, I chanced upon a book in a Mumbai airport store, The Loss of El Dorado by V.S. Naipaul. V.S. Naipaul, as some of you may know, is the 2001 Nobel Laureate in Literature. He was born and grew up in Trinidad, the grandson of servants to the British of East Indian origin during the time of the great colonies. Naipaul wrote several books on the history and culture of the Caribbean, and The Loss of El Dorado represents one of his finest works in this regard.

A paragraph in the foreword caught my attention:

“It was hard to feel any wonder at the fact that, more than four hundred years after Columbus, there were Indians in a part of the world he had called the Indies; and that the people he had called Indians had vanished. They had left no monuments; they were not missed.”

It was hard to feel any wonder … they were not missed. But why should there be wonder, contemplation and melancholic nostalgia of the past? In Bihari Trinidad, Naipaul was of, and observed, the first Indians of the new world in an India they had imagined. The land was not reluctant. There was no destruction and regeneration; it was not as if there was a past to be missed, but rather no such thing as a past. It is after all, a new world, and a new world was born there everyday.

As I proceeded to read The Loss of El Dorado, I was offered several philosophical viewpoints by the book. But Naipaul’s quote of the foreword, continued to strongly resonate. There was a certain deep fascination to the fact that when Columbus landed in Haiti and proclaimed it to be his India, he created a chain of events that would eventually bring Indians, including me, to the land of the Indies. Most surprisingly, and in some ways amusingly, living half way across the globe, the European notion, 500 years ago, that any land found in the Western quest of the Spanish was India, provides solace to the mind, substituting home sickness with home coming.

Are we strangers? Is this fascination just a consequence of cartographic limitations and anthropological errors of the European conquistadors? Rationally, it is easy to dismiss it so, but when we have a choice, we can transform it into the more human sensations of brotherhood. I would like to honour this feeling of cultural oneness today, through the vehicle of music, particularly the music of the Indians. And what better way to do it, but using the piano!

Pre-Columbian music had been adapted to European instruments ever since the Old and the New Worlds met. A famous example is Symphony No. 9 in E Minor (New World Symphony) of Antonin Dvořák, which he wrote on his visit to the plains. On December 15th, 1893, he writes in the New York Herald,

“I have simply written original themes embodying the peculiarities of the Indian music, and, using these themes as subjects, have developed them with all the resources of modern rhythms, counterpoint, and orchestral colour; the third movement scherzo was suggested by the scene at the feast in Hiawatha where the Indians dance.” [cite: Wikipedia]

In the same year, he said in a newspaper interview,

“I found that the music of the Negroes and of the Indians was practically identical”, and that “the music of the two races bore a remarkable similarity to the music of Scotland.” [cite: Wikipedia]

He also noted,

“I am convinced that the future music of this country must be founded on what are called Negro melodies. These can be the foundation of a serious and original school of composition, to be developed in the United States. These beautiful and varied themes are the product of the soil. They are the folk songs of America and your composers must turn to them.” [cite: Wikipedia]

For the most part, Dvořák’s predictions have come true. Since the birth of the popular era, the musical world has witnessed and cherished ragtime, rockabilly, rock and roll, jazz, blues, country, hip hop, mariachi, tango, salsa, samba, reggae; an endless list of musical genres that have their deepest roots in the West African and Aboriginal traditions of America.

Today, I have prepared to play a set of tunes, written by a little known musicologist, Gail Smith, whose book Native American Songs for Piano Solo I found and bought on Amazon. I have chosen three short pieces, originally written for the drum, the human voice and the flute, representing the three main instruments of the Indians.

The first piece, representing the drum is the Cherokee Deer Hunting Song:

The next piece is a Cheyenne lullaby:

And the final piece is a flute call by the Winnebago:

To end, let me quote from T.S. Elliot’s Little Gidding:

“We shall not cease from exploration
And the end of all our exploring
Will be to arrive where we started
And know the place for the first time.”

The fascinating beings that we are, we are often obliged to look back at history, and relive it differently in the future.



Written by sushilsub

August 21, 2014 at 10:53 pm

Saying Hello in the United States

leave a comment »

(Update: Results presented in this article have been used in the largest database of greetings in the various languages of the world. Please see Jennifer Runner’s page for the acknowledgements. Specifically, I contributed to Piscataway and Timucua translations.)

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.

(No copyrights; please cite, copy and distribute as much as required. Please leave a comment with contact information if you need a text or spreadsheet version.)

Languages List

Written by sushilsub

April 14, 2013 at 11:05 pm

Compressed Sensing: Transmit Nothing – Receive Everything

with 2 comments

(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.

The Paradigm Shift:

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:

Written by sushilsub

May 16, 2009 at 2:59 pm

Posted in Blog Entries

Tagged with ,


Get every new post delivered to your Inbox.