Black Lives Matter

Professor Rob Sellers, the Vice Provost for Equity and Inclusion and Chief Diversity Officer at University of Michigan, wrote a candid and unguarded reflection on the struggles of African-Americans today and throughout history. He wrote it 4 days after the death of George Floyd, as protests were spreading across the nation and the globe. Here is an excerpt:

"Some people argue that this country, while being built substantially by us, was never meant for us. (They are not wrong.) As such, some of these same people believe that other-worldly optimism is a sign of weakness and is ultimately what has sealed our fate as a people. They question the wisdom in holding out such faith and hope for change in a system (in a society) that has time and time again demonstrated that Black dignity, Black bodies, and Black lives matter a little less. (It is hard to argue with the logic of the question.)

"These times really do raise for me the question of how long must we wait, plan, work, march, agitate, forgive, and vote before we have a society in which all lives matter equally, regardless of race or color? In my bone-weary tired state this morning, before I even got out of bed, I asked myself why should I continue to fight to try to change a system that has proven time and time again that it simply does not regard me and people who look like me as fully human."

Professor Sellers' essay is not like the statements denouncing racism that I received from the university president, dean of my college, and chair of my department. It was honest, heartfelt, and raw. It touched me deeply and brought me sorrow.

It also made me proud to work alongside people like Professor Sellers in support of turning this country into a better place for everyone, especially African-Americans who have struggled for so long. Here are some existing projects at the University of Michigan with which you could potentially get involved -- or start your own.

Wolverine Pathways
M-STEM
Michigan Engineering Zone
AI4All

I believe engineering can provide many opportunities for underserved people, especially Black people, to build better lives and communities. I want to do that work alongside them, and I hope you join me.

US Women's Soccer -- World Cup Champions

I enjoyed reading several articles over the last 24 hours about the US Women's team's victory in the World Cup. This was one of my favorite.

From the article, a quote from Megan Rapinoe: “Getting to play at the highest level at a World Cup with a team like we have is just ridiculous,” Rapinoe said, “but to be able to couple that with everything off the field, to back up all of those words with performances, and to back up all of those performances with words, it’s just incredible.”

When I was a little girl playing soccer with a magazine spread of Mia Hamm's bicycle kick on my wall, I knew that women's soccer was something really special in the United States. But I wouldn't have guessed that it would someday become part of a bigger moment for equal rights in America (and the world), and that is now my hope.

I believe that we will win!

Blank page

“I'm writing a first draft and reminding myself that I'm simply shoveling sand into a box so that later I can build castles.”

― Shannon Hale

Writing can be very hard when you start with a blank page. I love this quote to help me get started.

Faster multiplies with (what else) the FFT

A friend sent me a great writeup of the new fastest known algorithm for multiplying two large numbers. Just like past fastest algorithms, it uses the Fast Fourier Transform, a clever algorithm for computing the Fourier Transform efficiently that was developed in 1965 (and a re-discovery of something Gauss originally developed in 1805). The Fourier Transform is simply a way of changing coordinate system of a signal to the Fourier domain, a beautiful and elegant coordinate system for representing the frequencies of a signal.

As the article points out, this new algorithm may only be used in a limited setting, as hardware implementation constraints dictate. But in cryptography or scientific computing, one may need to multiply extremely large numbers, and the hardware overhead of transferring to an on-chip FFT implementation may become worthwhile. The article itself points out that even the relative computational cost of multiplication versus addition has changed at the hardware level.

That said, the new algorithm achieves what people believe is the lower bound for multiplicative computations. Now on to proving that it is, indeed, the lower bound.

From the article:

On March 18, two researchers described the fastest method ever discovered for multiplying two very large numbers. The paper marks the culmination of a long-running search to find the most efficient procedure for performing one of the most basic operations in math.

...

In 1971 Arnold Schönhage and Volker Strassen published a method capable of multiplying large numbers in n × log n × log(log n) multiplicative steps, where log n is the logarithm of n. For two 1-billion-digit numbers, Karatsuba’s method would require about 165 trillion additional steps.

Schönhage and Strassen’s method, which is how computers multiply huge numbers, had two other important long-term consequences. First, it introduced the use of a technique from the field of signal processing called a fast Fourier transform. The technique has been the basis for every fast multiplication algorithm since.

Second, in that same paper Schönhage and Strassen conjectured that there should be an even faster algorithm than the one they found — a method that needs only n × log n single-digit operations — and that such an algorithm would be the fastest possible. Their conjecture was based on a hunch that an operation as fundamental as multiplication must have a limit more elegant than n × log n × log(log n).

“It was kind of a general consensus that multiplication is such an important basic operation that, just from an aesthetic point of view, such an important operation requires a nice complexity bound,” Fürer said. “From general experience the mathematics of basic things at the end always turns out to be elegant.”

Schönhage and Strassen’s ungainly n × log n × log(log n) method held on for 36 years. In 2007 Fürer beat it and the floodgates opened. Over the past decade, mathematicians have found successively faster multiplication algorithms, each of which has inched closer to n × log n, without quite reaching it. Then last month, Harvey and van der Hoeven got there.

Their method is a refinement of the major work that came before them. It splits up digits, uses an improved version of the fast Fourier transform, and takes advantage of other advances made over the past forty years. “We use [the fast Fourier transform] in a much more violent way, use it several times instead of a single time, and replace even more multiplications with additions and subtractions,” van der Hoeven said.

March is upon us

With March Madness right around the corner, I found this cool visualization of where top high school basketball players end up in the NBA: https://pudding.cool/2019/03/hype/.

I love the visualization. This is taking a single feature for each player -- at what level they are playing -- and visualizing its change over time with bouncing balls. It's not clear to me if the balls spend time at each relevant level, or if they just drop to the "current" or "final" level that the player achieved. The level is discretized, so this also allows for clear visualization. You can see that high school rank is correlated with final level -- but it's not perfect, and indeed the visualizations with lower-ranked players are also enlightening.

I'm looking forward to seeing where our Michigan players end up in the next few years and beyond!

An article in the Wall Street Journal last Saturday discussed Google's AI system called ARDA (Automated Retinal Disease Assessment) for diagnosing diabetic retinothapy. This sounds like an awesome tool -- and what I love to see -- showing that machine learning will make people's lives better in so many cases. Though, as many machine learning algorithms can be, it's sensitive to data quality. From the article:

"While ARDA is effective working with sample data, according to three studies including one published in the Journal of the American Medical Association, a recent visit to a hospital in India where it is being tested showed it can struggle with images taken in field clinics. Often they are of such poor quality that the Google tool stops short of producing a diagnosis—an obstacle that ARDA researchers are trying to overcome.

"The stakes are high. If diabetic retinopathy is caught early it can be kept at bay through monitoring and management of the diabetes, said R. Kim, an Indian ophthalmologist who runs the Aravind Eye Hospital in Madurai, Tamil Nadu, where Google is testing ARDA. More advanced stages need laser surgery that can stop progression. If it isn’t treated, the condition can cause blindness."

and later in the article:

"If Google allowed the algorithm to make a diagnosis from blurred images, it could miss small lesions that appear in the early stages of the condition, she said. Google must decide how bad an image can be before ARDA refuses to grade it. “It’s a trade-off. We want them to be able to use cameras that are a little harder to use but at some point it should move into something where it is ungradable,” Dr. Peng said."

This seems like an ideal setting for active learning, where the algorithm could request input from doctors when analyzing certain images. The algorithm should also train on blurrier or lower-quality but doctor-labeled images, so that it can learn some of the higher-level features that are indicative of retinopathy.

Still, props to all the companies working hard to improve the health of people around the world. It's a long road and I'm excited people are starting down it.

Dogs can't operate MRI scanners...

But catscan!! I need to start posting more -- what better way than to start with a bunch of puns! (That post is dead, let's try this one and see how long it lives)