Archive

Archive for the ‘Analysis’ Category

Robot stories

June 29, 2014 2 comments

Every summer before school was over, I was assigned a list of books to read. Mostly nonfiction and historical fiction, but in fourth grade there that was that first science fiction book. I often remember how that book made me feel, and marvel at the impact that it had in my life. I had read some science fiction before—Well’s Time Traveller and War of the Worlds—but this was different. This was a book with witty and thought-provoking short stories by Isaac Asimov. Each of them delivered drama, comedy, mystery and a surprise ending in about ten pages. And they had robots. And those robots had personalities, in spite of their very simple programming: The Three Laws of Robotics.

  1. A robot may not injure a human being or, through inaction, allow a human being to come to harm.
  2. A robot must obey the orders given to it by human beings, except where such orders would conflict with the First Law.
  3. A robot must protect its own existence as long as such protection does not conflict with the First or Second Law.

Back in the 1980s, robotics—understood as autonomous mechanical thinking—was no more than a dream. A wonderful dream that fueled many children’s imaginations and probably shaped the career choices of some. I know in my case it did.

Fast forward some thirty-odd years, when I met Astro: one of three research robots manufactured by the French company Aldebaran. This NAO robot found its way into the computer science classroom of Tom Simpson in Heathwood Hall Episcopal School, and quickly learned to navigate mazes, recognize some student’s faces and names, and even dance the Macarena! It did so with effortless coding: a basic command of the computer language python, and some idea of object oriented programming.

I could not let this opportunity pass. I created a small undergraduate team with Danielle Talley from USC (a brilliant sophomore in computer engineering, with a minor in music), and two math majors from Morris College: my Geometry expert Fabian Maple, and a McGyver-style problem solver, Wesley Alexander. Wesley and Fabian are supported by a Department of Energy-Environmental Management grant to Morris College, which funds their summer research experience at USC. Danielle is funded by the National Science Foundation through the Louis Stokes South Carolina-Alliance for Minority Participation (LS-SCAMP).

They spent the best of their first week on this project completing a basic programming course online. At the same time, the four of us reviewed some of the mathematical tools needed to teach Astro new tricks: basic algebra and trigonometry, basic geometry, and basic calculus and statistics. The emphasis—I need to point out in case you missed it—is in the word basic.

https://farm4.staticflickr.com/3921/14343225109_6d4c70558e_d.jpg

Talk the talk

The psychologist seated herself and watched Herbie narrowly as he took a chair at the other side of the table and went through the three books systematically.

At the end of half an hour, he put them down, “Of course, I know why you brought these.”

The corner of Dr. Calvin’s lip twitched, “I was afraid you would. It’s difficult to work with you, Herbie. You’re always a step ahead of me.”

“It’s the same with these books, you know, as with the others. They just don’t interest me. There’s nothing to your textbooks. Your science is just a mass of collected data plastered together by makeshift theory — and all so incredibly simple, that it’s scarcely worth bothering about.”

“It’s your fiction that interests me. Your studies of the interplay of human motives and emotions” – his mighty hand gestured vaguely as he sought the proper words.

Liar!
— Isaac Asimov

Astro can understand what I say, and maintain conversations with me. He has four microphones for voice recognition and sound localization, and two speakers for text-to-speech synthesis. But he sometimes gets confused: I say “acute”, and he understands “abide,” for example. This might sound frustrating by all standards. But mathematicians can’t be judged by any reasonable standard. Far from seeing this as a shortcoming, my team used as motivation the mechanics behind his speech recognition functionality, and they wrote some code to turn him into an expert Mastermind player.

Wait, what? How are these two things possibly connected?

Since Astro’s hearing is far from perfect, when he hears a word which is not clear, he gathers a short list of possible candidates. He then chooses the most likely guess based upon different considerations—using clues from context, for example. Based on similar strategies, he can be taught to be a perfect player of 5-letter-word Mastermind: Pick any five-letter word in the English language. Any word, provided it has no repeated letters. Astro chooses one random word as his first guess, and requests a score like in Mastermind.

To illustrate this process, I will show you how the game went when I chose Fabian’s favorite word: “acute.”

Astro: Is it firth?
Me   : NO
Astro: How many letters of my guess are in your word, in the right position?
       How many letters of my guess are in your word, in the wrong position?
Me   : 1, 0
Astro: Is it foams?
Me   : NO
Astro: How many letters of my guess are in your word, in the right position?
       How many letters of my guess are in your word, in the wrong position?
Me   : 0, 1
Astro: Is it junta?
Me   : NO
Astro: How many letters of my guess are in your word, in the right position?
       How many letters of my guess are in your word, in the wrong position?
Me   : 1, 2
Astro: Is it acute?
Me   : YES
Astro: Wonderful, I found it in 4 attempts!

I don’t want to get too technical here, but will mention some of the ideas. The main algorithm is based on techniques of numerical root finding and solving nonlinear equations — nothing complex: high-school level bracketing by bisection, or Newton’s method. To design better winning strategies, my team exploits the benefits of randomness. The analysis of this part is done with basic probability and statistics.

Walk the walk

Donovan’s pencil pointed nervously. “The red cross is the selenium pool. You marked it yourself.”

“Which one is it?” interrupted Powell. “There were three that MacDougal located for us before he left.”

“I sent Speedy to the nearest, naturally; seventeen miles away. But what difference does that make?” There was tension in his voice. “There are penciled dots that mark Speedy’s position.”

And for the first time Powell’s artificial aplomb was shaken and his hands shot forward for the man.

“Are you serious? This is impossible.”

“There it is,” growled Donovan.

The little dots that marked the position formed a rough circle about the red cross of the selenium pool. And Powell’s fingers went to his brown mustache, the unfailing signal of anxiety.

Donovan added: “In the two hours I checked on him, he circled that damned pool four times. It seems likely to me that he’ll keep that up forever. Do you realize the position we’re in?”

Runaround
— Isaac Asimov

Astro moves around too. It does so thanks to a sophisticated system combining one accelerometer, one gyrometer and four ultrasonic sensors that provide him with stability and positioning within space. He also enjoys eight force-sensing resistors and two bumpers. And that is only for his legs! He can move his arms, bend his elbows, open and close his hands, or move his torso and neck (up to 25 degrees of freedom for the combination of all possible joints). Out of the box, and without much effort, he can be coded to walk around, although in a mechanical way: He moves forward a few feet, stops, rotates in place or steps to a side, etc. A very naïve way to go from A to B retrieving an object at C, could be easily coded in this fashion as the diagram shows:

https://farm4.staticflickr.com/3884/14506683656_32784c832d_d.jpg

Fabian and Wesley devised a different way to code Astro taking full advantage of his inertial measurement unit. This will allow him to move around smoothly, almost like a human would. The key to their success? Polynomial interpolation and plane geometry. For advanced solutions, they need to learn about splines, curvature, and optimization. Nothing they can’t handle.

https://farm6.staticflickr.com/5595/14344128330_bb4845a89d_d.jpg

Sing me a song

He said he could manage three hours and Mortenson said that would be perfect when I gave him the news. We picked a night when she was going to be singing Bach or Handel or one of those old piano-bangers, and was going to have a long and impressive solo.

Mortenson went to the church that night and, of course, I went too. I felt responsible for what was going to happen and I thought I had better oversee the situation.

Mortenson said, gloomily, “I attended the rehearsals. She was just singing the same way she always did; you know, as though she had a tail and someone was stepping on it.”

One Night of Song
— Isaac Asimov

Astro has excellent eyesight and understanding of the world around him. He is equipped with two HD cameras, and a bunch of computer vision algorithms, including facial and shape recognition. Danielle’s dream is to have him read from a music sheet and sing or play the song in a toy piano. She is very close to completing this project: Astro is able now to identify partitures, and extract from them the location of the pentagrams. Danielle is currently working on identifying the notes and the clefs. This is one of her test images, and the result of one of her early experiments:

https://farm3.staticflickr.com/2906/14350961337_97bcb90e88_o_d.jpg https://farm4.staticflickr.com/3856/14537520835_4f0bf31eb1_d.jpg

Most of the techniques Danielle is using are accessible to any student with a decent command of vector calculus, and enough scientific maturity. The extraction of pentagrams and the different notes on them, for example, is performed with the Hough transform. This is a fancy term for an algorithm that basically searches for straight lines and circles by solving an optimization problem in two or three variables.

The only thing left is an actual performance. Danielle will be leading Fabian and Wes, and with the assistance of Mr. Simpson’s awesome students Erica and Robert, Astro will hopefully learn to physically approach the piano, choose the right keys, and play them in the correct order and speed. Talent show, anyone?

Advanced Problem #18

March 4, 2014 Leave a comment

Another fun problem, as requested by Qinfeng Li in MA598R: Measure Theory

Let f \in L_2(\mathbb{R}) so that g(x)=xf(x) \in L_2(\mathbb{R}) too.

Show that f \in L_1(\mathbb{R}) and \lVert f \rVert_1^2 \leq 8 \lVert f \rVert_2 \lVert g \rVert_2.

I got this problem by picking some strictly positive value \lambda and breaking the integral \int_{\mathbb{R}} \lvert f \rvert\, d\mu as follows:

\begin{array}{rl} \displaystyle{\int_{\mathbb{R}} \lvert f \rvert\, d\mu} &= \displaystyle{\int_{\lvert x \rvert \leq \lambda} \lvert f \rvert\, d\mu + \int_{\lvert x \rvert \geq \lambda} \lvert f \rvert\, d\mu} \\ \\   &= \displaystyle{\int_{-\lambda}^{\lambda} \lvert f \rvert\, d\mu + \int_{\lvert x \rvert \geq \lambda} \tfrac{1}{\lvert x \rvert} \lvert g(x) \rvert\, d\mu} \\ \\   &= \displaystyle{\int_\mathbb{R} \lvert f \rvert \cdot \boldsymbol{1}_{\lvert x \rvert \leq \lambda}\, d\mu + \int_{\mathbb{R}} \lvert g \rvert \cdot  \big( \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda}\big) \, d\mu} \\ \\   &\leq \lVert f \rVert_2 \cdot \big\lVert \boldsymbol{1}_{\lvert x \rvert \leq \lambda} \big\rVert_2 + \lVert g \rVert_2 \cdot \big\lVert \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda} \big\rVert_2 \end{array}

Let us examine now the factors \big\lVert \boldsymbol{1}_{\lvert x \rvert \leq \lambda} \big\rVert_2 and \big\lVert \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda} \big\rVert_2 above:

\big\lVert \boldsymbol{1}_{\lvert x \rvert \leq \lambda} \big\rVert_2 = \sqrt{2\lambda}

\big\lVert \tfrac{1}{\lvert x \rvert} \boldsymbol{1}_{\lvert x \rvert \geq \lambda} \big\rVert_2 = \displaystyle{ \sqrt{ 2\int_\lambda^\infty \dfrac{dx}{x^2}} = \sqrt{ \dfrac{2}{\lambda}} }

We have thus proven that f \in L_1(\mathbb{R}) with \lVert f \rVert_1 \leq \sqrt{2\lambda} \lVert f \rVert_2 + \sqrt{\tfrac{2}{\lambda}} \lVert g \rVert_2. At this point, all you have to do is pick \lambda = \lVert g \rVert_2 / \lVert f \rVert_2 (provided the denominator is not zero) and you are done.

Categories: Analysis, puzzles, Teaching

Book presentation at the USC Python Users Group

December 7, 2013 Leave a comment

Areas of Mathematics

October 22, 2013 3 comments

For one of my upcoming talks I am trying to include an exhaustive mindmap showing the different areas of Mathematics, and somehow, how they relate to each other. Most of the information I am using has been processed from years of exposure in the field, and a bit of help from Wikipedia.

But I am not entirely happy with what I see: my lack of training in the area of Combinatorics results in a rather dry treatment of that part of the mindmap, for example. I am afraid that the same could be told about other parts of the diagram. Any help from the reader to clarify and polish this information will be very much appreciated.

And as a bonus, I included a \LaTeX script to generate the diagram with the aid of the tikz libraries.

\tikzstyle{level 2 concept}+=[sibling angle=40]
\begin{tikzpicture}[scale=0.49, transform shape]
  \path[mindmap,concept color=black,text=white]
    node[concept] {Pure Mathematics} [clockwise from=45]
      child[concept color=DeepSkyBlue4]{
        node[concept] {Analysis} [clockwise from=180]
          child { 
            node[concept] {Multivariate \& Vector Calculus}
              [clockwise from=120]
              child {node[concept] {ODEs}}}
              child { node[concept] {Functional Analysis}}
              child { node[concept] {Measure Theory}}
              child { node[concept] {Calculus of Variations}}
              child { node[concept] {Harmonic Analysis}}
              child { node[concept] {Complex Analysis}}
              child { node[concept] {Stochastic Analysis}}
              child { node[concept] {Geometric Analysis}
                [clockwise from=-40]
                child {node[concept] {PDEs}}}}
          child[concept color=black!50!green, grow=-40]{ 
            node[concept] {Combinatorics} [clockwise from=10]
              child {node[concept] {Enumerative}}
              child {node[concept] {Extremal}}
              child {node[concept] {Graph Theory}}}
          child[concept color=black!25!red, grow=-90]{ 
            node[concept] {Geometry} [clockwise from=-30]
              child {node[concept] {Convex Geometry}}
              child {node[concept] {Differential Geometry}}
              child {node[concept] {Manifolds}}
              child {node[concept,color=black!50!green!50!red,text=white] {Discrete Geometry}}
              child {
                node[concept] {Topology} [clockwise from=-150]
                  child {node [concept,color=black!25!red!50!brown,text=white]
                    {Algebraic Topology}}}}
          child[concept color=brown,grow=140]{ 
            node[concept] {Algebra} [counterclockwise from=70]
              child {node[concept] {Elementary}}
              child {node[concept] {Number Theory}}
              child {node[concept] {Abstract} [clockwise from=180]
                child {node[concept,color=red!25!brown,text=white] {Algebraic Geometry}}}
              child {node[concept] {Linear}}}
    node[extra concept,concept color=black] at (200:5) {Applied Mathematics} 
      child[grow=145,concept color=black!50!yellow] {
        node[concept] {Probability} [clockwise from=180]
          child {node[concept] {Stochastic Processes}}}
      child[grow=175,concept color=black!50!yellow] {node[concept] {Statistics}}
      child[grow=205,concept color=black!50!yellow] {node[concept] {Numerical Analysis}}
      child[grow=235,concept color=black!50!yellow] {node[concept] {Symbolic Computation}};
\end{tikzpicture}

A nice application of Fatou’s Lemma

June 1, 2013 Leave a comment

Let me show you an exciting technique to prove some convergence statements using exclusively functional inequalities and Fatou’s Lemma. The following are two classic problems solved this way. Enjoy!

Exercise 1 Let {(X, \mathcal{F}, \mu)} be a measurable space and suppose {\{f_n\}_{n\in \mathbb{N}}} is a sequence of measurable functions in {L_1(\mu)} that converge almost everywhere to a function {f \in L_1(\mu)}, and such that the sequence of norms {\big\{ \lVert f_n \rVert_1 \big\}_{n \in \mathbb{N}}} converges to {\lVert f \rVert_1}. Prove that the sequence of integrals {\int_E \lvert f_n \rvert\, d\mu} converges to the integral {\int_E \lvert f \rvert\, d\mu} for every measurable set {E}.

Proof: Note first that

\displaystyle  \begin{array}{rcl}  \lvert f_n - f\rvert\, \boldsymbol{1}_E \leq \lvert f_n - f \rvert \leq \lvert f_n \rvert + \lvert f \rvert. \end{array}

Set then {g_n = \lvert f_n \rvert + \lvert f \rvert - \lvert f_n-f \rvert\, \boldsymbol{1}_E} (which are non-negative functions) and apply Fatou’s Lemma to that sequence. We have then

\displaystyle  \begin{array}{c}  \int_X \liminf_n g_n\, d\mu \leq \liminf_n \int_X g_n\, d\mu \\ \\ \int_X \liminf_n \big( \lvert f_n \rvert + \lvert f \rvert - \lvert f_n - f \rvert\, \boldsymbol{1}_E \big)\, d\mu \leq \liminf_n \int_X \big( \lvert f_n \rvert + \lvert f \rvert - \lvert f_n - f \rvert\, \boldsymbol{1}_E \big)\, d\mu \\ \\ \int_X \big( 2\lvert f \rvert - \limsup_n \lvert f_n-f \rvert\, \boldsymbol{1}_E\big)\, d\mu \leq \liminf_n \int_X \lvert f_n \rvert\, d\mu + \lVert f \rVert_1 - \limsup_n \int_E \lvert f_n -f \rvert\, d\mu \\ \\ 2\lVert f\rVert_1 \leq 2\lVert f \rVert_1 - \limsup_n \int_E \lvert f_n - f\rvert\, d\mu, \end{array}

which implies

\displaystyle  \begin{array}{rcl}  0 \leq \liminf_n \int_E \lvert f_n-f \rvert\, d\mu \leq \limsup_n \int_E \lvert f_n-f \rvert\, d\mu \leq 0. \end{array}

It must then be {\int_E \lvert f_n - f \rvert\, d\mu = 0}. But this proves the statement, since

\displaystyle  \begin{array}{c}  \bigg\lvert \int_E \lvert f_n\rvert\, d\mu - \int_E \lvert f \rvert\, d\mu \bigg\rvert = \bigg\lvert \int_E \big( \lvert f_n \rvert - \lvert f \rvert \big)\, d\mu \bigg\rvert \\  \leq \int_E \Big\lvert \lvert f_n \rvert - \lvert f \rvert \Big\rvert\, d\mu \leq \int_E \lvert f_n - f \rvert\, d\mu \end{array}

\Box

Exercise 2 Let {(X, \mathcal{F}, \mu)} be a finite measure space and let {1<p<\infty}. Suppose that {\{ f_n \}_{n \in \mathbb{N}}} is a sequence of measurable functions in {L_p(\mu)} whose norms are uniformly bounded in {n} and which converge almost everywhere to a function {f}. Prove that the sequence {\big\{ \int_X f_ng\, d\mu \big\}_{n \in \mathbb{N}}} converges to {\int_x fg\, d\mu} for all {g \in L_q(\mu)} where {q} is the conjugate exponent of {p}.

Proof: The proof is very similar to the previous problem. We start by noticing that under the hypotheses of the problem,

\displaystyle  \begin{array}{c}  \bigg\lvert \int_x f_ng\, d\mu - \int_X fg\, d\mu \bigg\rvert = \bigg\lvert \int_X (f_n -f)g\, d\mu \bigg\rvert \\ \leq \lVert (f_n-f)g \rVert_1 \leq \lVert f_n - f \rVert_p\, \lVert g \rVert_q. \end{array}

If we prove that {\lim_n \lVert f_n-f \rVert_p = 0}, we are done.

We will achieve this by using the convexity of {\lvert \cdot \rvert^p}, since in that case it is

\displaystyle  \begin{array}{rcl}  \frac{\lvert f_n - f \rvert^p}{2^p} \leq \tfrac{1}{2} \lvert f_n \rvert^p + \tfrac{1}{2} \lvert f \rvert^p. \end{array}

hence,

\displaystyle  \begin{array}{rcl}  \lvert f_n -f \rvert^p \leq 2^{p-1} \big( \lvert f_n \rvert^p + \lvert f \rvert^p \big). \end{array}

Set then {g_n = 2^{p-1} \big( \lvert f_n\rvert^p + \lvert f \rvert^p\big) - \lvert f_n-f \rvert^p} (which are non-negative functions) and apply Fatou’s Lemma as before. \Box

Have a child, plant a tree, write a book

April 23, 2013 2 comments

Or more importantly: rear your children to become nice people, water those trees, and make sure that your books make a good impact.

I recently enjoyed the rare pleasure of having a child (my first!) and publishing a book almost at the same time. Since this post belongs in my professional blog, I will exclusively comment on the latter: Learning SciPy for Numerical and Scientific Computing, published by Packt in a series of technical books focusing on Open Source software.

Keep in mind that the book is for a very specialized audience: not only do you need a basic knowledge of Python, but also a somewhat advanced command of mathematics/physics, and an interest in engineering or scientific applications. This is an excerpt of the detailed description of the monograph, as it reads in the publisher’s page:

It is essential to incorporate workflow data and code from various sources in order to create fast and effective algorithms to solve complex problems in science and engineering. Data is coming at us faster, dirtier, and at an ever increasing rate. There is no need to employ difficult-to-maintain code, or expensive mathematical engines to solve your numerical computations anymore. SciPy guarantees fast, accurate, and easy-to-code solutions to your numerical and scientific computing applications.

Learning SciPy for Numerical and Scientific Computing unveils secrets to some of the most critical mathematical and scientific computing problems and will play an instrumental role in supporting your research. The book will teach you how to quickly and efficiently use different modules and routines from the SciPy library to cover the vast scope of numerical mathematics with its simplistic practical approach that is easy to follow.

The book starts with a brief description of the SciPy libraries, showing practical demonstrations for acquiring and installing them on your system. This is followed by the second chapter which is a fun and fast-paced primer to array creation, manipulation, and problem-solving based on these techniques.

The rest of the chapters describe the use of all different modules and routines from the SciPy libraries, through the scope of different branches of numerical mathematics. Each big field is represented: numerical analysis, linear algebra, statistics, signal processing, and computational geometry. And for each of these fields all possibilities are illustrated with clear syntax, and plenty of examples. The book then presents combinations of all these techniques to the solution of research problems in real-life scenarios for different sciences or engineering — from image compression, biological classification of species, control theory, design of wings, to structural analysis of oxides.

The book is also being sold online in Amazon, where it has been received with pretty good reviews. I have found other random reviews elsewhere, with similar welcoming comments:

Trigonometry

June 22, 2012 Leave a comment

I have just realized that I haven’t posted a good puzzle here in a long time, so here it goes one on Trigonometry, that the average student of Calculus should be able to tackle: you can use anything you think it could help: derivatives, symmetry, periodicity, integration, summation, go to several variables, differential equations, etc

Prove that, for all real values x \in \mathbb{R}, it is

\sin x = x \cos\big(\tfrac{x}{2}\big) \cos\big(\tfrac{x}{4}\big) \cos\big(\tfrac{x}{6}\big) \cos\big(\tfrac{x}{8}\big) \dotsb \cos\big( \tfrac{x}{2n}\big) \dotsb

or, in a more compact notation,

\sin x = x \displaystyle{\prod_{n=1}^\infty \cos \big( \tfrac{x}{2n} \big)}

%d bloggers like this: