ChapterZero

Given a function , what kind of bounds can you put on the size of an interval where ? The fact that you can give a meaningful answer to this question is what allows for exact real arithmetic, because it allows you to perform exact operations on a number without knowing every digit of the number. That is, if we represent each number as a stream of digits, we can figure out how many digits of we need to determine the first digits of .

To answer the question, note that

We call the quantity the contractivity of over , and denote it by .

There is a clear correspondence between representing numbers as a sequence of digits and as nested intervals: iff for all . Therefore each number has a clearly defined head of digits for each integer , and the length of the corresponding interval is . So, to get the first digits of , we need to ensure

Using as an upper bound, we see that
is a sufficient condition.

I’ve been spending most of my time lately trying to figure out a way to visualize some volume data from the tissue segmentation project. The problem is, we have two images: the original and the processed; abnormally bright or light pixels in the processed image indicate that the tissue at that point is abnormal, and from looking at those pixels in the original image, we can determine whether the tissue is lipid or calcium. We’d like to color code lipid as yellow and calcium as blue. For 2d slices of the volume data, this is a trivial piece of Matlab code, and we can just as easily determine the color at each point in the volume, but it’s been proving extremely hard to find a program that can visualize it correctly.

It seems that most free volume visualization software is based on the principle of look up tables, which means they cannot use information on the location of a pixel to determine the color, only an intensity level in that pixel. Essentially, they assign colors by mapping from a grayscale range to the standard RGB space. This wouldn’t be so bad if I could render two volume images on top of each other– then I could have one representing the intensity of yellow and the other the intensity of blue. Unfortunately, this is yet another unavailable feature.

After Microview, OpenDX, and SciRun all turned out to be inadequate, I tried Teem and looked into VolPack. While not exactly a waste of time– definitely OpenDX seems to be worth investigation as a platform for any future visualization tasks I have, and Teem is attractive and powerful in the way only clever Unix commandline toolkits can be– I wasn’t able to find software that could solve my problem. Until today, when I ran across Andrew Winter’s vlib. If anything can solve my problem, that probably can. I didn’t know volume rendering could be so powerful– vlib seems to be able to serve as a general purpose renderer in the style of POV-Ray.

I just checked to see how much money I had in my school account, and realized I have enough to absorb the price of one quality math book. Since I’ve been getting back into computer algebra, and I’m reading Algorithms for Computer Algebra by Geddes, Czapor, and Labahn, I looked it up— guess how much that medium-sized book, with poor quality typsetting costs?

More than $100! In fact, most of the results I got back (abebooks) were over $300! What is up with that? I also looked up a really comprehensive general algebra book– I mean, read it and understand it, and you’ll know more than enough algebra for any non-algebraic discipline– Advanced Modern Algebra by Rotman, and it costs under $70. Rotman’s book is larger, has a more beautiful cover, is beautifully typeset, and covers way more material than Geddes, et. al. Yet it costs much less.

The only reason I can think of for this is the absolute dearth of good introductory level texts on computer algebra. After reading Geddes, et. al., I feel like I’ll be able to go out and code up a better CAS than say, Yacas. It is about the only resource for this purpose I came across worth mentioning, and from what I’ve seen, is heavily cited. Sad that it came out in 1992 and still has no competition worth mentioning. Apparently the publishers realize this. Someone should write a free book on computer algebra, so people like myself don’t have to dish out money we don’t have.

So, I won’t be buying any math books this season.

It’s sad how hard it is to get good information on the TeX system. Getting information on the basic programs: tex and metafont, isn’t hard at all– Knuth took care of that with four books, and even an extra one on the Computer Modern fonts, so you can see how to use metafont. But past that, the infrastructure that has grown up around TeX is bewildering, and depressingly underdocumented.

My acquaintance with this fact was just renewed, as I looked for font metric information on the Bakoma Computer Modern TrueType families. In the end, I just gave up, not least of all because I couldn’t find the information I’m looking for. The bitmap files metafont produces are so much better documented. Put those together with Appendix G of the TeXbook, and I should be able to emulate the TeX display engine well enough for the purposes of a CAS front end (something along the lines of JSMath).

Yep, I’ve a one track mind, and it has brought me back to that old horse. I’m once again attempting to produce a universal CAS frontend. I’ve decided to make it reliant on Metafont for font production; that’ll mean users will have to have a working metafont installation, but it also means that accurate metric information will be available for every different font size, and it opens up the possibility for later increasing compatibility with TeX. My initial goal is to make the system capable of displaying mathematical expressions with the same quality as TeX, but I see no reason why in the future it could not come closer to being a full TeX implementation.

I just finished grading the last two assignments for this semester: it took me more than 5 hours, but now I’m done until next year. On the other hand, I’m broke, because I was so busy studying for finals and doing research that I didn’t turn in my timesheets, so I’ve missed *3* paychecks!

Now I’m starting to look back into BasicCAS. I printed out the code a few days ago so I can refamiliarize myself with the product of my genius. I’ve also been reading Computing with Real Numbers with the intention of implementing an exact arithmetic background for BasicCAS. Not because I need to– there are a couple of C libraries out there I could call from Python– but because I’d like to learn the concepts behind it. I’ve read a significant portion of the paper, and I still don’t see how the structure they’re building (a system for manipulating digit streams based on linear fractional transformations) will lead to an exact arithmetic system. It’s a cliff-hanger!

I’m going to implement the arithmetic system in pure Python first, and then write it up in C so when BasicCAS is used in C-based Pythons there is the option for increased speed. I also intend to rework the parser to make it more Mathematica compatible.

Other than that, over the break I’m going to be working a lot on the DCA, since I finally have time. In fact, that’s what I’m off to do right now. It looks like the high pass channel may contain nothing but noise, so we may drop it from consideration in the algorithm.

I’ve been working on a digital contrast agent for detecting early signs of early signs of arthereosclerosis non-invasively through 3d CT scans(currently impossible), with Dr. Papadakis (probably lately, the most mentioned name here :)), since September of this year. The technique we’re using is a combination of stochastic modeling and wavelet decomposition. Specifically, we apply a nonseparable wavelet transform to the entire 3d volume scan of a coronary artery, and assume that each individual tissue corresponds to a texture, which we consider to be random field. We assume that the individuality of each texture is preserved across the scales. We require the end user of the algorithm to provide us with a small region of the volume that is known or assumed to be ‘normal’ tissue, and fit a linear predictive filter over each subband of this image. By running these filters over the entire volume, and considering the difference between the actual and predicted wavelet coefficients, we can isolate the ‘abnormal’ portions of the image, and reconstruct these.

Today we had a major breakthrough: we have what looks like the first evidence of the algorithm differentiating between classes of soft tissues. Until now, we were having much more success at locating calcium that anything else, but that is of limited use, since current thresholding techniques can already isolate calcium deposits. I am very impressed with these results! See the magic for yourself (below the fold: the images are huge).

The top image is the original CT data, which has no visible difference between types of tissues, the second is the actual histology, where you can observe several large lipid pools, and the bottom is the CT image processed using our algorithm.

(more…)

Dr. Johnson, one of my favorite profs at UH, gave me a bibliography of fractional calculus. This was prompted by one of my essays for the NSF fellowship: I asked him to write a recommendation for me, and I mentioned that in my first class, we were supposed to learn about fractional derivatives, but never did. I think it’s cool that my comment moved him to supply me with a starting point for looking into it myself.

Apparently, fractional derivatives have been motivated by the question: “Can the meaning of derivatives of integral order be extended to have meaning when is any number, real, complex, and irrational?” Nothing under the sun is new: Liouville published several memoirs on the topic beginning back in 1832.

It’s interesting how I’ve never heard about fractional derivatives from anyone other than Johnson. Perhaps, as he intimated, the course of mathematics is influenced more by fads than any more objective reason. But then again, what would such an objective reason be? The most obvious candidate, scientific application, is not really as objective as it would seem: physical problems can usually be approached from several different directions, with correspondingly different tools.

I’ve been thinking about current mathematical fads I’m aware of: chaos theory, game theory, wavelets. I’m sure there are more. The question worth considering is, which will survive their 15 minutes of fame?