Scroll to the bottom of the page for the Math Geek Adventures blog archive.

Tuesday, July 30, 2013

Math Blog #2. How to Solve an Inverse Problem: Regularization

In my last math blog, I introduce what an inverse problem is. We used the notation 

(1) z=Au,

and said that the goal is to estimated u given z and A, where A is assumed to be a linear operator.

We also said that in inverse problems, our interest is on solving problems of the form (1) that fail one of the three conditions for well-posedness: (i) existence of a solution u; (ii) uniqueness of that solution; and (iii) continuous dependence of the solution u on z and A.

If (i) or (ii) fails, we can solve instead

u_ls = {argmin_u ||Au-z||^2 s.t. ||u|| is minimized}.

This minimum norm least squares solution is given by

(2) u_ls =pinv(A'*A)*(A'*z)    

where pinv denotes psuedo-inverse.

If (iii) fails, the mapping (A,z)-->u_ls defined by (2) is discontinuous, and we have to use regularization to make the problem well-posed. Tikhonov was one of the first to address this issue. He suggested solving instead

(3) u_alpha = argmin_u {||Au-z||^2 + alpha*||u||^2},

which is known as Tikhonov regularization. Problem (3) is now well-posed with a unique solution  

u_alpha = (A'*A+alpha*I)\(A'*z),

where \ denotes multiplication by the inverse matrix.

Red Mountain, Highland Range, Butte Montana

During the Butte 50 race, I was running support for Jen. I was meeting her at the Highland Aid Station (the third aid station for the 50) and so had 4+ hours to kill while she made her way there from the start at Homestake. Since Red Mountain is only a few miles from Highland Station, I opted to bag the peak and go a bit beyond. To get to the aid station, you go out old highway 2 from Butte and take the road heading right at the bottom of Pipestone Pass. Follow the main road for quite a few miles (approx. 10) until you come out in a mountain meadow with a camp ground/parking area on your right. This is where the CDT crosses the road and is where the aid station is located during the race. Turn left here and follow the signs (staying left) for Highland Lookout about 3 or 4 miles. After a cattle guard, there's a road to the right. This goes up to Highland Lookout.

Red Mountain is an easy walk up. I continued on to Monument Peak (approx. 1 hour round trip from Red) and would have like to also bag Table (probably approx. 1 hour round trip from Monument), but would have missed Jen if I had continued on. If you're in the area it's a worthwhile outing. Red and Table are the prominent peaks that you see when you look south from Butte.

Pudge, Highland Lookout, then Red Mountain

Highland Lookout looking north. No longer in use. In the 90s when I used to come up here it was still in use.

Highland Lookout from Red Mountain.

Table Mountain in back, and Monument (the pyramidal shaped) Peak from Red Mountain, looking south.

Pudge, looking south to Table from Monument.

Pudge looking north from Monument, Red Mountain in the background

Friday, July 26, 2013

Flinsch Peak, Glacier National Park

This week, we did a 3-day backpack with Ellie and her friend Skye Everett. It was an awesome trip, with perfect weather and really fun 13-year old girls. On day 2, hiking from Old Man to No Name Lakes, I took the side trip to summit Flinsch Peak. Here it is from Old Man Lake, where we camped the first night.
Flinsch Peak from Old Man Lake.
It looks pretty technical, but the back side is a walk-up most of the way with only the top bit being technical, as you'll see in a moment. On day 2, we hiked up over Pitamakan Pass, then traversed to Dawson Pass. This section of trail rivals any I've been on for scenery, including all of the tramps we did in New Zealand.

Flinsch Peak from Pitamakan Pass. That's me, Ellie, Skye and Jen.
Ellie, Skye and Flinsch Peak

Dropped my pack on Dawson Pass for some peak baggin'
The next picture shows that Flinsch Peak isn't a walk up the whole way. The last 50-100 feet are potentially dangerous -- the rock is loose and a fall could be lethal -- and require extreme caution, though an experienced mountaineer or rock climber would find this section straightforward.

I followed my nose and a climber path up the scree to this cliff, which required a few exposed moves to reach the top.
Old Man Lake and Pitamakan Pass looking northwest.

looking west, Mt. Stimson on the far left.

look southwest, Mt. Stimson on the far right.

Looking south into the Great Bear and Bob Marshall.

looking Southeast, Two Medicine Lake on the left, No Name lake under the cliff in shadow.

looking east out to the Plains

close up of that shot south

A Conversation With Alex

I had to get this down for posterity. It is an interaction I had with Alex while he's at bike camp in Colorado. He might be a natural psychologist. 

Alex: I broke my axel and had to get it fixed at a bike shop.
Me: How much was it?
Alex: Fifty bucks.
Me: Really, that's pretty cheap. 
Alex: That was just for the part.
Me: What was it, seventy bucks total with installation? 
Alex: No, it was eighty to a hundred. 
Me: Sounds like you know exactly how much it was, why don't you tell me?
Alex: It was a hundred.

Wednesday, July 17, 2013

Math Blog #1. What is an Inverse Problem?

Inspired by a mini-symposium I visited at the 2013 SIAM Annual Meeting devoted to having a web presence as a research mathematician, I've decided to start doing periodic blogs with a mathematical bent. This one is the first.

My research area is inverse problems, which is broad in the sense that it overlaps with a variety of mathematical areas, from pure analysis, to applied mathematics, statistics, physics, engineering, and computer science, to name a few. But the international community of inverse problems researchers is not huge.

What are inverse problems? Consider for a moment the equation


where z is function representing an observed quantity (the collected image in astronomy or x-ray intensities in a CT scan); u is a function representing the unknown that we want to estimate (a higher resolution image in astronomy or the actual CT scan the doctor looks at); and A is the mathematical operator mapping u to z.

Inverse problems encompass a broad range of problems, but traditionally they are ill-posed, which means NOT well-posed. Well-posed problems were defined mathematically by Hadamard.

DEFINITION: The equation z=Au is well-posed if
1. for all z, there is a solution u such that z=Au;
2. the solution u is unique for all z;
3. the solution u depends continuously on z.

In my mind, it is really the lack of satisfying #3 that characterizes an inverse problem. Problems that don't satisfy #1 and/or #2 appear in many areas, for example, in basic linear models in stastics. A linear problem that fails #1 and/or #2, but not #3, can be made well-posed by computing the minimum norm, least squares solution, for example. But if #3 doesn't hold, the inverse mapping from z to u is unstable in finite dimensions and discontinuous in infinite dimensions. In such cases, a separate class of methods, known as regularization, must be used to make the problem well-posed.

NOTE: in practice, I have no problem with the broad use of  term 'inverse problem' to include problems ranging from small-scale, nonlinear parameter estimation, to problems that only fail #1 and/or #2, it's just that in my mind, it is the failure of #3 that makes inverse problems a unique discipline. 

Monday, July 15, 2013

Music Motivates Work: Finland Tunes

In Helsinki, I worked 25 straight days and so needed any motivation I could find to stay productive. Since the body can only take so much caffeine, I've had to find some other drivers. Lately, I've been using music to this effect. Music that's got an energy, but isn't too in your face; electronica and jazzy rap works for me. Here's a music compilation of the artists/albums I listened to a lot in Helsinki: Daft Punk's new album, Bonobo's new album, Jay Dilla, and Common. Here's the mix: Finland 2013Warning: some of the rap songs have explicite lyrics.

Wednesday, July 10, 2013

Conference Travel: Part of Being a Research Mathematican

There are many parts to being a scientist. I use the term scientist because it's broad, and I think that the comments I'll make here extend across disciplines, and also because we mathematicians view our work as science, even if we're not always directly applying the scientific method when we're doing research.

From the outside, mathematics seems to be a solitary discipline. There's much truth to this notion, but it's also a very social discipline, both in the sense that you've got to see what others are doing to be inspired, and also because work is typically better done in groups, the whole being greater than it's parts. Indeed, in this day and age, many of the important problems mathematicians are tackling could not be solved by a single person.

Conferences serve the purpose of bringing researchers of a similar mind together, to share ideas and to be inspired by one another. By now, I have been to many conferences, and I do find that they achieve their purpose, but they are also lonely places. You typically find yourself sequestered away in some hotel, with a lot of free time between the talks that really interest you. In the past, conferences have been places where I've gotten work done.

I am currently at the SIAM (Society for Industrial and Applied Mathematics) Annual Meeting in San Diego. It's been good: I've given a talk and seen some great ones. And the family is along, which makes the trip much more enjoyable and less lonely than usual.

Monday, July 8, 2013

Mt. Howe, Pintlers

Pudge, Mt. Howe (nearest) and Mt. Evans (behind) from Little Rainbow Mtn.
I've had a disposable camera sitting in the bottom of my backpacking pack for a couple of years now, waiting to be developed. It contains shots from a solo day trip that I took to climb Mt. Howe in the Pintlers. I'd been waiting to write this blog until I got the film developed, but instead, in honor of the highcountry clearing, I'm taking advantage of some spare moments in the early morning to write this, on a conference trip to California with the family. If I ever get the film developed, I'll supplement the ones I've included, which are from an overnight excursion to Storm Lake with the family last fall.

There are a number of ways to climb Mt. Howe. If you look on SummitPost, for example, they recommended route is from the south and Seymour Creek. Whereas Ecorover, master of all things Pintler, takes the route less traveled, from the east, up Sullivan Creek. Being a busy Missoulian, I started from the over-used Storm Lake trailhead, and headed east toward Mt. Howe. At about the one mile mark, you come to a saddle with this awesome view of Mt. Howe. She's a true and classic beauty!
Mt. Howe with Jen in the foreground.

At this point, I headed off trail, for the saddle between Howe and Little Rainbow Mtns. The route consists of rugged, loose, steep, and mildly dangerous skree travel. The other (less rugged, but longer) option was to first summit Little Rainbow Mtn. (where the first photo above was taken), heading east from the Goat Flat trail, and then continue along the ridge to Howe. But I was keen to try the direct route. No matter which way I travel in these surprisingingly rugged peaks, after slipping on scree and slicing open my knee (needing multiple stitches) while summitting Mt. Evans (Howe's neighbor) a few years back, I always travel with care.

Sunday, July 7, 2013

Book Review: Canada, by Richard Ford

Richard Ford is probably my favorite author. His darkish sensibility, at least what comes through in his books, agrees with my own. His protagonists tend to be passive observers of the events of their life veering (or having had veered) off course. In his brilliant Sportswriter (Frank Bascombe) Triology, the protagonist Frank is a primary instigator of this veering. While in Canada, the protagonist Dell is a 15 year old boy, who watches his parents take their family from normal – his Dad an Air Force Captain at the base in Great Falls, his mother a home maker, he and his sister – to disintegration with one incredibly bad decision.

The reader comes to understand that Dell’s dad, though a decorated and long serving military man, has always had a leaning toward crime. He starts at the base with a small-scale scam that eventually loses him his job. Then, after some months of trying civilian work life (selling cars and real-estate), he gets involved in another scam, becomes indebted to some dangerous individuals, and makes the outlandish decision to rob a bank to cover his modest debt. He is somehow able to convince his sensible wife to help him. They rob the bank, get caught, and the kids go from dreams about hobbies and anticipating school starting in a couple of weeks to being suddenly on their own.

While his sister runs off, being the good son, Dell sticks around and waits for his mother’s friend to whisk him away. The woman takes him north into Canada, to her brother who is an eccentric that has also run from his past in the States, and where it quickly becomes apparent that Dell’s days of observing, and experiencing the consequences of, the bad decisions of adults is not yet over.

Perhaps the main message of the novel is Ford’s insistence that normality and ruin run right up next to each other (even mix together) and are sometimes separated by only a few bad decisions. But also the resiliency of the human spirit and the positive consequences of just a bit of good luck, especially in a young person that is curious about life, is eager to learn, and is willing to remain optimistic through seemingly hopeless situations.
Anyway, the book is ambitious, and Ford pulls it off. The fact that he soldiers on, plying his craft as masterfully as ever at nearly 70, is a gift, and it also makes him an inspiration.