598 – Upcoming talk: Jodi Mead

October 28, 2009

Jodi Mead, Wed. November 4, 2:40-3:30 pm, MG 120.

Non-smooth Solutions to Least Squares Problems

In an attempt to overcome the ill-posedness or ill-conditioning of inverse problems, regularization methods are implemented by introducing assumptions on the solution.  Common regularization methods include total variation, L-curve, Generalized Cross Validation (GCV), and the discrepancy principle. It is generally accepted that all of these approaches except total variation unnecessarily smooth solutions, mainly because the regularization operator is in L^2. Alternatively, statistical approaches to ill-posed problems typically involve specifying a priori information about the parameters in the form of Bayesian inference. These approaches can be more accurate than typical regularization methods because the regularization term is weighted with a matrix rather than a constant. The drawback is that the matrix weight requires information that is typically not available or is expensive to calculate.

The \chi^2 method developed by the author and colleagues can be viewed as a regularization method that uses statistical information to find matrices to weight the regularization term.  We will demonstrate that unique and simple L^2 solutions found by this method do not unnecessarily smooth solutions when the regularization term is accurately weighted with a diagonal matrix.

502 – Cancellation laws

October 28, 2009

Two homework problems. The first one is easier, so you can consider the second one to be extra credit. A proof of these results can be found in different places, for example, the paper Division by three, by Conway and Doyle. (Please don’t look at the paper while working on the homework, of course.) Unfortunately, the paper could use a serious trimming and editing, so I cannot really recommend it, but the proof is carefully written there.

  1. Without using the axiom of choice, show that if A and B are sets, and |A\times 2|=|B\times 2|, then |A|=|B|.
  2. Same as 1., but now with 3 instead of 2. 

598 – Upcoming talk: Jens Harlander

October 21, 2009

Jens Harlander, Wed. October 28, 2:40-3:30 pm, MG 120.

Introduction to Computational Complexity

Complexity theory provides ways of measuring the difficulty of computational mathematics problems. Some problems are indeed impossibly difficult (your Math 108 and 143 students are right after all!). For example, there does not exist an algorithm that decides whether a polynomial (in an arbitrary number of variables) with integer coefficients has integer roots. However for many difficult problems, simple strategies work well in practice as long as one is willing to ignore a hopefully sparse set of inputs. I will discuss basic features of the theory, give you more examples of impossibly hard problems and tell you about the relevance of all of this to Internet security.

598 – Schedule of talks

October 20, 2009

Here is the list of speakers for the rest of the term. 

175 – Quiz 4

October 18, 2009

Here is quiz 4.

Read the rest of this entry »

502 – More on tilings

October 16, 2009

In class I mentioned without proof that there is a finite set of squares with which we can tile the plane, but not periodically. Hao Wang was the first to study the question of whether there are such tilings. He conjectured that the answer was not. In 1966, his student Robert Berger disproved the conjecture. He explained how tiles could be used to code the workings of a formalized computer (a Turing machine), in a way that one could solve recursively the Halting Problem if it were the case that any set that tiles can do so periodically. Since it is a well-known result from computability theory that the halting problem cannot be solved recursively, it follows that Wang’s conjecture is false.

Examining the tiling given by Berger, one finds that he requires 20426 tiles to do his coding. The number has been substantially reduced since. I believe the currently known smallest set of tiles that can only cover the plane aperiodically has size 13. It was exhibited by Karel Culik II in his paper An aperiodic set of 13 Wang tiles, Discrete Mathematics 160 (1996), 245-251. The Wikipedia entry on Wang tiles displays his example. Once again, the proof of aperiodicity uses the halting problem.

(I would be curious to know of improved bounds.)

502 – Ordinal exponentiation

October 16, 2009

The exercise I mentioned in class is the following: Let \alpha^{\cdot\beta} denote ordinal exponentiation. For ordinals \alpha,\beta, define F(\alpha,\beta) as the set consisting of those functions f:\beta\to\alpha such that there are only finitely many \xi such that f(\xi)\ne0. 

(We haven’t formally defined “finite” yet, but we can take this to mean that the order type of the set \{\xi\in\beta\mid f(\xi)\ne0\} is a natural number, using our formalized notion of natural number.)

For functions f,g in F(\alpha,\beta) set f\triangleleft g iff f(\xi)<g(\xi) for \xi largest such that f(\xi)\ne g(\xi).

Then (F(\alpha,\beta),\triangleleft) is a well-ordered set, and its order type is precisely \alpha^{\cdot\beta}.