Archive for the ‘Women and Math’ Category.

Reverse Bechdel Test

A movie passes the Bechdel Test if these three statements about it are true:

  • There are at least two named women in it
  • Who talk to each other
  • About something besides a man.

Surely there should be a movie where two women talk about the Bechdel test. But I digress.

The Bechdel test website rates famous movies. Currently they have rated 4,683 movies and 56% pass the test. More than half of the movies pass the test. There is hope. Right? Actually they have a separate list of the top 250 famous movies. Only 70 movies, or 28%, from this list pass the test.

My son Alexey suggested the obvious reverse Bechdel test, which is more striking than the Bechdel test. A movie doesn’t pass the test if it

  • Has at least two named men characters
  • Whenever they talk to each other
  • They only talk about women.

I can’t think of any movie like that. Can you?


Next Tanya Khovanova

Many years ago at Gelfand’s seminar in Moscow, USSR, someone pointed out a young girl and told me: “This is Natalia Grinberg. In her year in the math Olympiads, she was the best in the country. She is the next you.”

We were never introduced to each other and our paths never crossed until very recently.

Several years ago I became interested in the fate of the girls of the IMO (International Math Olympiad). So, I remembered Natalia and started looking for her. If she was the best in the USSR in her year, she would have been a gold medalist at the IMO. But I couldn’t find her in the records! The only Grinberg I found was Darij Grinberg from Germany who went to the IMO three times (2004, 2005, and 2006) and won two silver medals and one gold.

That was clearly not Natalia. I started doubting my memory and forgot about the whole story. Later I met Darij at MIT and someone told me that he was Natalia’s son.

I was really excited when I received an email from Natalia commenting on one of my blog posts. We immediately connected, and I asked her about past events.

Natalia participated in the All-Soviet Math Olympiads three times. In 1979 as an 8th grader she won a silver medal, and in 1980 and 1981 she won gold. That indeed was by far the best result in her year. So she was invited to join the IMO team.

That year the IMO was being held in the USA, which made Soviet authorities very nervous. At the very last moment four members of the team did not get permission to travel abroad. Natalia was one of them. The picture below, which Natalia sent to me, was taken during the Soviet training camp before the Olympiad. These four students were not allowed to travel to the IMO: Natalia Grinberg, Taras Malanyuk, Misha Epiktetov, and Lenya Lapshin.

1981 IMO training camp

Because of the authorities’ paranoia, the Soviet team wasn’t full-sized. The team originally contained eight people, but as they rejected four, only six traveled to the USA, including two alternates.

I have written before how at that time the only way for a Jewish student to get to study mathematics at Moscow State University was to get to the IMO. I wrote a story about my friend Sasha Reznikov who trained himself to get to the IMO, but because of some official machinations, still was not accepted at MSU.

Natalia’s story surprised me in another way. She didn’t get to the IMO, but she was accepted at MSU. It appears that she was accepted at MSU as a member of the IMO team, because that decision was made before her travel documents were rejected.

Natalia became a rare exception to the rule that the only way for a Jewish person to attend MSU was to participate in the IMO. It was a crack in the system. They had to block visas at the last moment, so that people wouldn’t have time to make a fuss and do something about it. Natalia slipped through the crack and got to study at the best university in the Soviet Union.

Unfortunately, the world lost another gold IMO girl. Three Soviet team members won gold medals that year. Natalia, being better then all of them, would have also won the gold medal.


The Best Math Problem Solver is a Girl

At the 2011 IMO, Lisa Sauermann received yet another gold medal. Now she tops the Hall of Fame of the IMO with four gold medals and one silver medal.

In addition, in 2011 she achieved the absolute best individual result and was the only person with a perfect score. In previous years, there were several girls who tied for first place, but she is the first girl ever to have an absolute rank of 1.

I told you so. In my 2009 essay Is There Hope for a Female Fields Medalist?, I predicted that a girl will soon become an absolute champion of the IMO.

In that essay I draw a parallel between the absolute champion of IMO and a Fields medalist. Indeed, we get one of each per year. Lisa Sauermann is the best math problem solver in her year. Will she grow up to receive a Fields medal? I am not so sure: the medal is still unfriendly to women. Lisa Sauermann is the best math problem solver ever. Will she grow up to be the best mathematician of our century? I wonder.


Polite Gender Bias

From time to time my female colleagues share stories with me of great unfairness or horrible sexual harassment in the world of mathematics. I can’t reciprocate — certainly not on that level.

I do not have any horror stories to tell. Generally I am treated with great respect, at least to my face. In fact, some men have told me that I am the smartest person they ever met.

The stories I want to share are not about harassment. No single incident is a big deal. But when these things happened time after time after time, I realized: this is gender bias.

First story. A guy told me, “Your proof is unbelievably amazing.”

What can I say? It is just a compliment. Though I am not sure why the word “unbelievable” was included. Is it difficult to believe that I can produce an amazing proof? I encounter surprise too often to my taste.

Second story. Another guy tells me after I explain a solution to a math problem, “I didn’t realize it was so simple.”

Actually it wasn’t simple. When I explained the solution, it may have seemed simple, but that was because I was able to explain it to him with such clarity. People tend to downgrade their opinion of the problem, rather than upgrade their opinion of my ability. It actually affects my reputation as a mathematician.

Third story. Another guy said to me (and I quote!), “I am so dumb. I tried for a week to write the program that computes these numbers and you did it in one hour. I feel so dumb. I didn’t expect myself to be so dumb. Why am I so dumb?”

After the fourth “dumb”, I started wondering what it was all about. Many guys try to compete with me. And they hate losing to a woman. It creates a strong motivation for them to discard my brilliance and to explain away my speed, even if they have to claim temporary dumbness.

Fourth story. Someone asked me, “What is the source of the solutions and math ideas in your blog? Can you refer me to the literature?”

I do invest extra effort in citing the sources of the math puzzles I discuss. Everything else — the solutions, the ideas, new definitions, new sequences — I invent myself. I have even started inventing math puzzles. This is my blog. I thought of it myself, I wrote it myself. Has anyone ever asked Terence Tao where he takes the solutions for his blog from?

Unfortunately, this attitude damages my career. When people think that my ideas come from someone else, they do not cite me.

But all these stories however minor happen all the time, not only to me but to all my female colleagues. Gender bias is real. Next time someone tells me how unbelievably amazing my proof is, I will explode.


Math as an Aphrodisiac

In my life as a female mathematician I have quite often encountered a mathematician’s wife who, despite not knowing me, already hated me. It was clear that it had nothing to do with me personally, so being clueless and naive, I assumed that most men were cheaters and that their wives were extremely insecure and jealous.

Then one day one of the wives decided to be frank about her feelings. It wasn’t about cheating, she told me. It was that she felt distant from her husband. He lived in a world of mathematics from which she was excluded. I on the other hand shared this world with him.

It was very sad. It meant that I incurred their jealousy, not because of my sins, but because I am a female mathematician.

Let me tell you another story that helped me realize how all-encompassing this world of mathematics can be for some people. Once I had a very close friend who we will call Jack. I do not want to name him as he is a famous mathematician. Jack told me that the strongest emotions he feels are related to mathematics. He can only feel close to someone if he can share a mathematical discussion with them.

Now I understand the wives better. Husbands like Jack invest so much more in their math world and their colleagues than they do in their home life, that it is not surprising the wives are jealous. Because women mathematicians are scarce, when I appear in their husbands’ world, it adds another layer of worry.

Another thing that Jack told me is that he gets such a euphoric feeling when he discovers a new math idea that it is better than any orgasm. Of course, this statement made me question the quality of Jack’s orgasms, but in any case, for some mathematicians math is an aphrodisiac.

If math is an aphrodisiac, then tattooing a formula on the lover’s body may well enhance the orgasm. I just remembered the movie by Ed Frenkel. But I digress.

If math is an aphrodisiac, then I understand jealous wives even better. Without sex I can give their husbands pleasure they can’t.


Why Are We Losing Female Mathematicians?

Sanya Took an IntegralThe data from annual surveys carried out by the American Mathematical Society shows the same picture year after year: the percentage of females in different categories decreases as the category level rises. For example, here is the data for 2006:

Category Percentage of Women
Graduating Math Majors 41
PhDs Granted 32
Fresh PhD hires in academic jobs 27
Full-time Faculty 27
Full-time tenured or tenure-track faculty 12

The high percentage of female math majors means that a lot of women do like mathematics. Why aren’t women becoming professors of mathematics? In the picture to the left, little Sanya fearlessly took her first integral. I hope, even as an adult, she will never be afraid of integrals.

I am one of the organizers of the Women and Mathematics Program at the Institute for Advanced Study at Princeton In 2009 we had a special seminar devoted to discussing this issue. Here is the report of our discussion based on the notes that Rajaa Al Talli took during the meeting.

Many of us felt, for the following three reasons, that the data doesn’t represent the full picture.

First, the different stages correspond to women of different ages; thus, the number of tenured faculty should be compared, not to the number of current math majors, but rather to women who majored in math many years ago. The percentage of female PhDs in mathematics has been increasing steadily for the past several years. As a result, we expect an eventual increase in the number of full-time female faculty.

Second, international women mathematicians might be having a great impact on the numbers. Let’s examine a hypothetical situation. If many female professors come to the US after completing their studies in other countries, it would be logical to assume that they would raise the numbers. But since the numbers are falling, we might be losing more females than we think. Or, it could be the opposite: international graduate students complete a PhD in mathematics in the USA and then go back to their own countries. In this case we would be losing fewer females to professorships than the numbers seem to suggest. Unfortunately, we can’t really say which case is true as we do not know the data on international students and professors.

Third, many women who major in mathematics also have second majors. For example, the women who have a second major in education probably plan to become teachers instead of pursuing an academic career. It would be interesting to find the data comparing women who never meant to have careers in science with those women who left because they were discouraged. If we are losing women from the sciences because they decide not to pursue scientific careers, then at least that is their choice.

It is also worth studying why so few women are interested in careers in mathematics in the first place. Changing our culture or applying peer pressure in a different direction might change the ambitions of a lot of people.

We discussed why the data in the table doesn’t represent the full picture. On the other hand, there are many reasons why women who can do mathematics and want to do mathematics might be discouraged from pursuing an academic career:

  • Marriage and children distract from mathematics.
  • The lack of legal protections for pregnant women, of required maternity leave and of childcare provision.
  • The cultural skepticism that women can do math on a high level.
  • An educational system that tends to tell students that math is very difficult, thus discouraging women from the early stages of their academic life.
  • Boys tend to be more competitive than girls.
  • The lack of job opportunities.
  • A career in math often requires moving.

Our group proposed many solutions to help retain women in mathematics:

  1. Find a way to get men pregnant as well.
  2. Incorporate ideas from other countries (like Portugal), where they don’t have this problem.
  3. Increase the level of social care for pregnant women and young children.
  4. Create new laws to protect the rights of pregnant women.
  5. Educate secondary, high school and college math teachers how to present math — such as through games — as an interesting subject, not as a difficult one.

At the end of our meeting, everyone accepted Ingrid Daubechies‘ proposal that we do the following:

Each woman in mathematics should take as her responsibility the improvement of the mathematical environment in which she works. If every woman helps change what’s going on in her university or the school where she teaches, that will help solve the problem on the larger scale.


Should You Date a Mathematician?

The book How to Drive Your Man Wild in Bed by Graham Masterton has a chapter on how to choose a lover. It highlights red flags for men who need to be approached with caution. There is a whole list of potentially bad signs, including neglecting to shower in the previous week and talking only about himself.

The list of bad features also includes professions to avoid. Can you guess the first profession on the list? OK, I think you should be able to meta-guess given the fact that I am writing about it. Indeed, the list on page 64 starts:

Avoid, on the whole, mathematicians…

I am an expert on NOT avoiding mathematicians: in fact, I’ve married three of them and dated x number of them. That isn’t necessarily because I like mathematicians so much; I just do not meet anyone else.

When I was a student I had a theory that mathematicians are different from physicists. My theory was based on two conferences on mathematical physics I attended in a row. The first one was targeted for mathematicians and the second for physicists. The first one was very quiet, and the second one was all boozing and partying. So I decided that mathematicians are introverts and physicists are extroverts. I was sure then that my second husband chose a wrong field, because he liked booze and parties.

By now, years later, I’ve met many more mathematicians, and I have to tell you that they are varied. It is impossible and unfair to describe mathematicians as a type. One mathematician even became the star of an erotic movie. I write this essay for girls who are interested in dating mathematicians. I am not talking about math majors here, I am talking about mathematicians who do serious research. Do I have a word of advice?

I do have several words of caution. While they don’t apply to all mathematicians, it’s worth keeping them in mind.

First, there are many mathematicians who, like my first husband, are very devoted to mathematics. I admire that devotion, but it means that they plan to do mathematics on Saturday nights and prefer to spend vacation at their desks. If they can only fit in one music concert per year, it is not enough for me. Of course, this applies to anyone who is obsessed by his work.

Second, there are mathematicians who believe that they are very smart. Smarter than many other people. They expand their credibility in math to other fields. They start going into biology, politics and relationships with the charisma of an expert, when in fact they do not have a clue what they are talking about.

Third, there are mathematicians who enjoy their math world so much that they do not see much else around them. The jokes are made about this type of mathematician:

What is the difference between an extroverted mathematician and an introverted one? The extroverted one looks at your shoes, rather than at his own shoes.

Yes, I have met a lot of mathematicians like that. Do you think that their wives complain that their husbands do not notice their new haircuts? No. Such triviality is not worth mentioning. Their wives complain that their husbands didn’t notice that the furniture was repossessed or that their old cat died and was replaced by a dog. My third husband was like that. At some point in my marriage I discovered that he didn’t know the color of my eyes. He didn’t know the color of his eyes either. He wasn’t color-blind: he was just indifferent. I asked him as a personal favor to learn the color of my eyes by heart and he did. My friend Irene even suggested creating a support group for the wives of such mathematicians.

While you need to watch out for those traits, there are also things I like about mathematicians. Many mathematicians are indeed very smart. That means it is interesting to talk to them. Also, I like when people are driven by something, for it shows a capacity for passion.

Mathematicians are often open and direct. Many mathematicians, like me, have trouble making false statements. I stopped playing —Mafia— because of that. I prefer people who say what they think and do not hold back.

There is a certain innocence among some mathematicians, and that reminds me of the words of the Mozart character in Pushkin’s poetic drama, Mozart and Salieri: —And genius and villainy are two things incompatible, aren’t they?— I feel this relates to mathematicians as well. Many mathematicians are so busy understanding mathematics, they are not interested in plotting and playing games.

Would I ever date a mathematician again? Yes, I would.


The Second IMO Gold Girl

Me in 1975Janet Mertz encouraged me to find IMO girls and compare their careers to that of their teammates. I had always wanted to learn more about the legendary Lida Goncharova — who in 1962 was the first girl to win an IMO gold medal. So I located her, and after an interview, wrote about her. Only 14 years later, in 1976, did the next girl get a gold medal. That was me. I was ranked overall second and had 39 points out of 40.

As I did in the article about Lida, I would like to compare my math career to that of my teammates.

I got my PhD in 1988 and moved to the US in 1990. My postdoc at MIT in 1993 was followed by a postdoc at Bar-Ilan University. In 1996 I got a non-paying visiting position at Princeton University. In 1998 I gave up academia and moved to industry, accepting an offer from Bellcore. There were many reasons for that change: family, financial, geographical, medical and so on.

On the practical level, I had had two children and raising them was my first priority. But there was also a psychological element to this change: my low self-esteem. I believed that I wasn’t good enough and wouldn’t stand a chance of finding a job in academia. Looking back, I have no regrets about putting my kids first, but I do regret that I wasn’t confident enough in my abilities to persist.

I continued working in industry until I resigned in January 2008, due to my feeling that I wasn’t doing what I was meant to do: mathematics. Besides, my children were grown, giving me the freedom to leave a job I did not like and return to the work I love. Now I am a struggling freelance mathematician affiliated with MIT. Although my math blog is quite popular and I have been publishing research papers, I am not sure that I will ever be able to find an academic job because of my non-traditional curriculum vitae.

The year 1976 was very successful for the Soviet team. Out of nine gold medals our team took four. My result was the best for our team with 39 points followed by Sergey Finashin and Alexander Goncharov with 37 points and by Nikita Netsvetaev with 34 points.

Alexander Goncharov became a full professor at Brown University in 1999 and now is a full professor at Yale University. His research is in Arithmetic Algebraic Geometry, Teichmuller Theory and Integral Geometry. He has received multiple awards including the 1992 European Math Society prize. Sergey Finashin is very active in the fields of Low Dimensional Topology and Topology of Real Algebraic Varieties. He became a full professor at Middle East Technical University in Ankara, Turkey in 1998. Nikita Netsvetaev is an expert in Differential Topology. He is a professor at Saint Petersburg State University and the Head of the High Geometry Department.

Comparing my story to that of Lida, I already see a pattern emerging. Now I’m curious to hear the stories of other gold-winning women. I believe that the next gold girl, in 1984, was Karin Gröger from the German Democratic Republic. I haven’t yet managed to find her, so can my readers help?


Lida Goncharova — The First Gold IMO Girl

LidaJanet Mertz wrote several papers about the gender gap in mathematics. One of her research ideas was to find girls who went to the International Math Olympiad (IMO) and compare their fate to that of their teammates with a similar score. She asked me to find Soviet and Russian IMO girls. All my life I had heard about Lida Goncharova, the first girl on a Soviet team, and the first girl in the world who took a gold medal, but I had never dared to reach out to her. A little push by Janet Mertz was enough for me to find Lida’s phone number in Moscow and call her.

My conversation with Lida Goncharova


Lida got interested in mathematics when she was five years old. Luckily, many of her relatives were mathematicians and she started bugging them for math puzzles.

Her involvement with math was interrupted by the death of her parents — her mother when she was seven, and her father when she was nine. She ended up living with her sister, but felt very lonely.

After several years of personal turmoil, she renewed her pursuit of mathematics. Lida started discussing math with her mother’s first husband. She joined a math circle which was run at Moscow State University. When she was 13 she went to a summer camp and found a mentor there to study trigonometry. Eventually she ended up at School Number 425, one of the first schools in Moscow that opened for children gifted in math.

At the end of high school she went to the IMO as part of the Soviet team and won a gold medal there. After that she enrolled in the most prestigious Soviet institute for the study of math — Moscow State University (MSU).

Half of her high school classmates went to MSU, including her high school sweetheart Alexander Geronimus. Lida married Alexander when she was a sophomore and they had their first son in her fourth year of undergraduate school.

Meanwhile, she wasn’t doing as well in her studies as she had hoped. Lida was very fast to pick up math ideas during conversations, but she had difficulty reading books. As ideas were becoming more complicated and involved, this became a problem. She started feeling that she was falling behind her friends. When her friends gathered together to discuss mathematics she couldn’t understand everything. She wanted to ask questions, but was too shy. Plus, she didn’t want to impose on them. She made a decision to be silent. As a result she started ignoring the conversations of others and became discouraged as she fell behind.

She had her second child at the beginning of graduate school, where she studied under the supervision of Dmitry Fuchs. Lida was already losing her self-esteem and so she chose a self-contained problem that didn’t require a lot of outside knowledge. The solution involved some combinatorial methods, but Lida didn’t quite understand the big picture and the problem’s goal.

I contacted Dmitry Fuchs and asked him about Lida’s thesis. He told me that Lida’s main result is extremely important and widely cited. It is called Goncharova’s theorem.

Meanwhile, her husband finished his PhD in math and secured a great job in an academic institution. They had started as peers, but her work was interrupted by having their children. Lida finished her PhD a couple of years after her husband and got a very boring job as an algorithm designer. She even wrote some papers at the job, but she was not much interested. She continued her attempts to do mathematics and continued asking everyone for problems, but it didn’t go anywhere. Her friends were not very interested in her calculations and after the birth of her third child she began to lose hope in her research.

When Lida and her husband entered graduate school they became religious. Ten years later, Alexander decided to pursue the Russian Orthodox religion as a career and got a parish in 600 km from Moscow. They didn’t want to move their children away from Moscow, with its educational and cultural opportunities. So they started living in two places with long commutes. This didn’t help her math either.

Eight years after the third son, the fourth son was born. Although Lida sporadically continued her calculations, she still didn’t talk about them to anyone.

When the older children went to high school, Lida enjoyed solving their math problems tremendously. In 1990 perestroika started and Lida lost her job. She got an offer to create a private school and teach there. By this time she had had two more children, a son and a daughter. Lida continued working for the private school until her six children grew out of it. Lida enjoyed teaching and inventing methods to teach mathematics. The school ended in 2004. But she continues working with kids sharing with them her joy of mathematics.

Lida believes that she has had an extremely lucky life in many ways. The only exception was her unsuccessful math career. She can’t live without math, and will continue working with kids, solving fun problems and doing her private research.

When I first called her and said I wanted to talk about her and math, she told me: —There is nothing to talk about. I stopped doing math after my PhD. Almost.— That —almost— kept me asking questions.

Lida’s teammates


Janet Mertz was considering a serious research project comparing the fates of IMO medal girls with the fates of their teammates, to see whether gender plays a role later. However, due to the language and cultural differences and the fact that most of the girls changed their last name, it was difficult to locate them. So Mertz put this research project on hold.

She had asked me to find and contact the Russian women and I was so fascinated with Lida’s story that I decided to write it up in this article. And because the research is on hold, I decided to include the fates of Lida’s teammates.

Lida Goncharova got her gold medal in the 1962 IMO with 42 points and was ranked third. The teammate with the closest score was Joseph Bernstein with another gold medal and 46 points. I don’t even have to check Wikipedia to tell you about Joseph, as I was once married to him. He used to be a professor at Harvard University and is now a professor at Tel-Aviv University. He is a member of the Israel Academy of Sciences and Humanities and the United States National Academy of Sciences. He achieved a lot and is greatly respected by his peers.

Joseph Bernstein might not be the best person to compare Lida to as he had a perfect score. Some might argue that a perfect score indicates that he might have done better if the problems had been more difficult.

The two Soviet teammates whose scores were the closest to that of Lida, but below her, were Alexey Potepun with 37 points and Grigory Margulis with 36 points.

Alexei Potepun got a PhD in mathematics and is now a professor at Saint-Petersburg University. He has published eleven papers.

Next to Alexey Potepun is Grigory Margulis, who is a professor at Yale and was awarded the Fields Medal and the Wolf Prize. He is a member of the U.S. National Academy of Sciences.

You might notice that the two people who moved to the US are much more famous than those who stayed in Russia. You might say that moving to the US is a better predictor of success than gender. Sure, living in a free country helps, but Margulis got his Fields medal while he was in the USSR. And Bernstein invented his famous D-Modules while in Russia also.

My conversation with Lida was personally inspiring. I loved the tone of her voice when she talked about mathematics. There were many elements that prevented her from having the mathematical career she might have had: the untimely death of her parents, her shyness, raising six children, many years of long commutes. When we look at the achievements of her closest teammates, we can’t help but wonder what kind of mathematics we lost.

This conversation was very encouraging for me. I felt there were similarities between Lida and myself in more ways than I expected. What we share most of all is a love for mathematics. I could hear that in her voice.


Sparsity and Computation

Once again I am one of the organizers of the Women and Math Program at the Institute for Advanced Study in Princeton, May 16-27, 2011. It will be devoted to an exciting modern subject: Sparsity and Computation.

In case you are wondering about the meaning of the picture on the program’s poster (which I reproduce below), let us explain.

WaM 2011 Poster Picture

The left image is the original picture of Fuld Hall, the main building on the IAS campus. The middle image is a corrupted version, in which you barely see anything. The right image is a striking example of how much of the image can be reconstructed from the corrupted image using clever algorithms.

Female undergraduates, graduates and postdocs are welcome to apply to the program. You will learn exactly how the corrupted image was recovered and much more. The application deadline is February 20, 2011.

Eugene Brevdo generated the pictures for our poster and agreed to write a piece for my blog explaining how it works. I am glad that he draws parallels to food, as the IAS cafeteria is one of the best around.

by Eugene Brevdo

The three images you are looking at are composed of pixels. Each pixel is represented by three integers corresponding to red, green, and blue. The values of each integer range between 0 and 255.

The image of Fuld hall has been corrupted: some pixels have been replaced with all 0s, and are therefore black; this means the pixel was not “observed”. In this corrupted version, 85% of the pixel values were not observed. Other pixels have been modified to various degrees by stationary Gaussian noise (i.e. independent random noise). For the 15% observed pixel values, the PSNR is 6.5 db. As you can see, this is a badly corrupted image!

The really interesting image is the one on the right. It is a “denoised” and “inpainted” version of the center image. That means the pixels that were missing were filled in and the observed pixel integer values were re-estimated. The algorithm that performed this task, with the longwinded name “Nonparametric Bayesian Dictionary Learning,” had no prior knowledge about what “images should look like”. In that sense, it’s similar to popular wavelet-based denoising techniques: it does not need a prior database of images to correct a new one. It “learns” what parts of the image should look like from the original image, and fills them in.

Here’s a rough sketch of how it works. The idea is to use a new technique in probability theory — the idea that a a patch, e.g. a contiguous subset of pixels, of an image is composed of a sparse set of basic texture atoms (from the “Dictionary”). Unfortunately for us, the number of atoms and the atoms themselves are unknowns and need to be estimated (the “Nonparametric Learning” part). In a way, the main idea here is very similar to Wavelet-based estimation, because while Wavelets form a fixed dictionary, a patch from most natural images is composed of only a few Wavelet atoms; and Wavelet denoising is based on this idea.

We make two assumptions that allow us to simplify and solve this problem, which is unwieldy-sounding and vague when the texture atoms have to be estimated. First, there may be many atoms, but a single patch is a combination of only a sparse subset of them. Second, because each atom appears in part in many patches, even if we observe some noisily, once we know which atoms appear in which patches, we can invert and average together all of the patches associated with an atom to estimate it.

To explain and programmatically implement the full algorithm that solves this problem, probability theorists like to explain things in terms of going to a buffet. Here’s a very rough idea. There’s a buffet with a (possibly infinite) number of dishes. Each dish represents a texture atom. An image patch will come up to the buffet and, starting from the first dish, begins to flip a biased coin. If the coin lands on heads, the patch takes a random amount of food from the dish in front of it (the atom-patch weight), and then walks to the next dish. If the coin lands on tails, the patch skips that dish and instead just walks to the next. There it flips its coin with a different bias and repeats the process. The coins are biased so the patch only eats a few dishes (there are so many!). When all is said and done, however, the patch has eaten a random amount from a few dishes. Rephrased: the image patch is made from a weighted linear combination of basic atoms.

At the end of the day, all the patches eat their own home-cooked dessert that didn’t come from the buffet (noise), and some pass out from eating too much (missing pixels).

If we know how much of each dish (texture atom) each of the patches ate and the biases of the coins, we can estimate the dishes themselves — because we can see the noisy patches. Vice versa, if we know what the dishes (textures) are, and what the patches look like, we can estimate the biases of the coins and how much of a dish each patch ate.

At first we take completely random guesses about what the dishes look like and what the coins are, as well as how much each patch ate. But soon we start alternating guesses between what the dishes are, the coin biases, and the amounts that each patch ate. And each time we only update our estimate of one of these unknowns, on the assumption that our previous estimates for the others is the truth. This is called Gibbs sampling. By iterating our estimates, we can build up a pretty good estimate of all of the unknowns: the texture atoms, coin biases, and the atom-patch weights.

The image on the right is our best final guess, after iterating this game, as to what the patches look like after eating their dishes, but before eating dessert and/or passing out.