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.

Advertisement

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}.


502 – Infinite well-ordered sets

October 9, 2009

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

Suppose that (A,<) is an infinite well-ordered set, and that B\subseteq A. Show that there is a bijection between A and the disjoint union A\sqcup B.

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 (A,<) is a well-ordered set, then there is a well-ordered set (B,\prec) such that (A,<) is a proper initial segment of (B,\prec) and there is no injection from B into A. 


175 – Integrating products of secants and tangents

October 9, 2009

(In what follows, I will write {\tan^n x} for {(\tan x)^n} and {\sec^m x} for {(\sec x)^m.})

Recall that

\displaystyle  \tan x=\frac{\sin x}{\cos x}\quad\mbox{ and }\quad\sec x=\frac1{\cos x},

that

\displaystyle  (\tan x)'=\sec^2x\quad\mbox{ and }\quad(\sec x)'=\sec x\cdot\tan x,

and that

\displaystyle  \sec^2x=\tan^2x+1.

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

\displaystyle  \int \sec^m x\cdot \tan^n x\,dx,

for {m} and {n} integers, {m,n\ge0.}

Read the rest of this entry »


502 – Ultraproducts of finite sets

October 2, 2009

I want to sketch here the proof that if {(M_n\mid n\in{\mathbb N})} is a sequence of finite nonempty sets, and {\lim_n |M_n|=\infty,} then {\prod_nM_n/{\mathcal U}} has size {|{\mathbb R}|} for any nonprincipal ultrafilter {{\mathcal U}} on {{\mathbb N}.}

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 {\kappa,} then {\kappa^{\aleph_0}=\kappa.} His argument is a very nice application of non-standard analysis. The case that interests us is easier.

Clearly,

\displaystyle |\prod_nM_n/{\mathcal U}|\le|\prod_n M_n|\le|{\mathbb N}^{\mathbb N}|=|{\mathbb R}|,

so it suffices to show that {|{\mathbb R}|\le|\prod_nM_n/{\mathcal U}|.}

Read the rest of this entry »