598 – Upcoming talk: Jodi Mead

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 . 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 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  solutions found by this method do not unnecessarily smooth solutions when the regularization term is accurately weighted with a diagonal matrix.

502 – Cancellation laws

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 and are sets, and then
2. Same as 1., but now with instead of  

598 – Upcoming talk: Jens Harlander

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

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

• Jens Harlander, October 28.
• Jodi Mead, November 4.
• Leming Qu, November 11.
• Grady Wright, November 18.
• Marion Scheepers, December 2. 
• Laurie Cavey, December 9.

175 – Quiz 4

Here is quiz 4.

502 – More on tilings

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

The exercise I mentioned in class is the following: Let denote ordinal exponentiation. For ordinals , define as the set consisting of those functions such that there are only finitely many such that  

(We haven’t formally defined “finite” yet, but we can take this to mean that the order type of the set is a natural number, using our formalized notion of natural number.)

For functions in set iff for largest such that

Then is a well-ordered set, and its order type is precisely

502 – Infinite well-ordered sets

I just want to record the Exercise I mentioned in class:

Suppose that is an infinite well-ordered set, and that Show that there is a bijection between and the disjoint union

To be explicit, I want a proof that makes no use of the axiom of choice. Also, although I am not requiring this as an exercise, recall that the point is to use this result to complete the proof of the following:

Theorem. If is a well-ordered set, then there is a well-ordered set such that is a proper initial segment of and there is no injection from into  

175 – Integrating products of secants and tangents

(In what follows, I will write for and for )

Recall that

that

and that

The formulas below make use of these identities repeatedly.

We want a series of methods and reduction formulas that allow us to evaluate any expression of the form

for and integers,

502 – Ultraproducts of finite sets

I want to sketch here the proof that if is a sequence of finite nonempty sets, and then has size for any nonprincipal ultrafilter on

The argument I present is due to Frayne, Morel, Scott, Reduced direct products, Fundamenta Mathematica, 51 (1962), 195–228.

The topic of the size of ultraproducts is very delicate and some open questions remain. For ultraproducts of finite structures, this is continued in Keisler, Ultraproducts of finite sets, The Journal of Symbolic Logic, 32 (1967), 47–57, and finally in Shelah, On the cardinality of ultraproduct of finite sets, The Journal of Symbolic Logic, 35 (1) (Mar., 1970), 83–84. Shelah shows that if an ultraproduct of finite sets is infinite, say of size then His argument is a very nice application of non-standard analysis. The case that interests us is easier.

Clearly,

so it suffices to show that