TIL: The column space and null space

A vector space is a set of vectors that is closed under addition and scalar multiplication. In other words, given two vectors, v and w,  a vector space is formed by the set of all linear combinations formed between v and w, namely cv + dw for arbitrary coefficients c and d.

Columns spaces and null spaces are special categories of vector spaces that have interesting properties related to systems of linear equations, Ax = b. The column space of the matrix A, C(A), is simply the linear combinations of A's column vectors. This implies that Ax = b may only be solved when b is a vector in A's column space. Finally, the null space of matrix A is another vector space formed by all the solutions to Ax = 0.

TIL: a principled approach to dynamic programming

Dynamic programming has always been a topic I understood at a surface level (it's just memoization, right?!), but ultimately feared for lack of real-world experience solving such problems. I read today a superb explanation of a principled approach to solving dynamic programming problems. Here it is:

1. Try to define the problem at hand in terms of composable sub-problems. In other words, ask yourself what information would make solving this problem easier?
2. Define a more rigorous recurrence relation between the sub-problems and the current problem. What are the base-cases and how do the sub-problems answer the current problem?
3. Build a solution look up table (up to the point of the current problem) by first initializing it for the base cases and then for the sub-problems in a bottom-up approach. The bottom-up approach is the defining characteristic of a dynamic programming solution. Alone, the look up table is just memoization. Note: building the solution table bottom up will often look like a post-order depth-first search.

Here is an implementation (in Scala) to the following problem:

Given a general monetary system with M different coins of value {c1, c2, . . . , cM}, devise an algorithm that can make change for amount N using a minimum number of coins. What is the complexity of your algorithm?

TIL: Alpha-to-coverage for order-independent transparency

Alpha-to-coverage is a computer graphics technique, supported by most (all?) modern GPUs, for rendering translucent multi-sampled anti-aliased primitives. Given an alpha value in the range of [0.0, 1.0] and N samples of color stored per pixel, the alpha channel will be discretized into a coverage-mask of the N samples. An alpha of 0 will generate an empty coverage-mask (no samples take on the new color), an alpha of 1 will result generate a full coverage-mask (all samples take on the new color), and values in between will generate a partial coverage-mask (between 1 and N-1 samples take on the new color).

It's not alpha-to-coverage itself that I learned today however, but rather it's implication; Alpha-to-coverage is a form of order-independent transparency! In the naïve case, one benefits from N-layers of transparency. I suppose this is the whole point of alpha-to-coverage, but I never put two-and-two together*.

* I blame my experience. Being a GPU driver engineer, but never a rendering engineer, I'm exposed to large cross-section of rendering techniques and low-level graphics implementation details, but never to the greater-picture of real-time rendering but by word of mouth and self-study.

TIL: Today I learned

It has been a long time since my last appearance. I've written a couple of unfinished posts in that time, but I've realized that writing a detailed essay that's up to a satisfactory standard of quality is actually quite time consuming (who would have thought!). In an attempt at more productive writing, I will try to publish one post per day expounding on something new I've learned that day. Nothing more than a paragraph or two. My hope is that this will be burden-free enough not to require extraneous effort, yet valuable enough that it's worth recording. Equally, this will serve as a nice personal journal of my educational journey post-schooling.

Encapsulation == Parameterization

Martin Odersky recently made the interesting observation that encapsulation is equivalent to parameterization. He demonstrated this by showing how abstract types are used (in their natural fashion) for encapsulation in Scala, and then equivocated parameterized types (aka generic classes) to corresponding types where the original type parameters had been transformed into abstract type members.

Intuitively this observation makes sense. Encapsulation's goal is to hide information: don't let me muck with the internals of an implementation. Parameterization's goal on the contrary is to defer, or put another way abstract, implementation details (i.e. abstract what types or values make up the data structure or algorithm that I'm building). Logically, as we increase the amount of parameters, the less we can know. That is to say, by restricting our knowledge we've abstracted, or hidden, implementation details from ourselves! (albeit, in a somewhat inverse manner than traditional encapsulation, but that's besides the point)

As we can see clearly now, encapsulation and parameterization are equivalent; both hide implementations and both abstract interfaces. Put another way, hiding implementations is equivalent to abstracting interfaces.

"Is President Obama Really A Socialist? Let's Analyze Obamanomics" -- Reactions

I wrote this in response to a post of a Facebook friend the other night. It was never meant to be more than some casual thoughts, and still really, it's only that. However, seeing as I'm awful at staying current on my blog, I thought I might as well not let this digital hunk of "ideas to paper" go to complete waste. So, here it is, a reaction to silly political Forbes article, (almost) completely unedited.

---

There is a lot wrong (or perhaps misguided, in my opinion) in this article. It's hard to know where to start. However, let me start by saying that what follows is simply to point out the holes of Ferrara's arguments from a factual standpoint, as it is presented; In no way am I asserting that if we accept what he says to be wrong, then the logical implication is that Obama's solutions are automatically right. In fact, I'm not going to talk to Obama's policies at all. So, let's begin.

the top 1% of income earners paid 39% of all federal income taxes, three times their share of income at 13%. Yet, the middle 20% of income earners, the true middle class, paid just 2.7% of total federal income taxes on net that year, while earning 15% of income. 

His line of reasoning here only works if you agree that every dollar has equal worth (which, they don't[1]). In that case, what he puts foward does suggest that there is a flaw *somewhere* in the system; I don't think anyone is denying that. However, what is more startling are the ratios between percentage of income to percentage of income earners. The difference between (13/1) and (15/30) means that the top 1% is making 1700% more than the middle 20%! And that's only with the conservative bounds that Farrara has chosen. That gap will certainly expotentially increase as you widen the bounds to include the lower class and the upper class (1% is what I would call "elite upper class").

Any normal person would say that such an income tax system is more than fair, or maybe that “the rich” pay more than their fair share.

Yes, perhaps so, but "any normal person" isn't qualified to make these judgements (we like to think we are, though). Economics, like any other science, is non obvious; that's why we have economists and trained professionals. Anyways, point is: the "any normal person would..." card is a straw-man's argument.

The answer is that to President Obama this is still not fair because he is a Marxist.  To a Marxist, the fact that the top 1% earn more income than the bottom 99% is not fair, no matter how they earn it, fairly or not.  So it is not fair unless more is taken from the top 1% until they are left only with what they “need,” as in any true communist system.  Paying anything less is not their “fair” share.  __That is the only logical explanation of President Obama’s rhetoric__, and it is 100% consistent with his own published background.

No it's not. Like most things in this world, there isn't a binary right or wrong, yes or no, "this way or that way answer" solution or answer to everything (or most things for that metter). Following that, his jump to "Obama is a Marxist" is a long leap to make and equally ignorant (I actually doubt this man is ignorant, but rather knows his readers well).

Good tax policy is not guided by “need.”  It is guided by what is needed to establish the incentives to maximize economic growth.

Says who? (no, seriously) There's a lot of debate about this, but I hardly think what he suggests here is a "good thing"(™). A tax policy that optimizes only for "economic growth" doesn't speak at all to economic distribution. In my book (okay, I'm interjecting an opinion here), a good tax policy would ensure the largest amount of people are living comfortable, with small but noticeable degrees of variance -- the variance allowing for the opportunity to achieve greater economic success (i.e. to ensure that the motivation to "rise the ranks" still exists, a key component of the "American Dream").

The middle class, working people and the poor are benefited far more by economic growth than by redistribution.  That is shown by the entire 20th century, where the standard of living of American workers increased by more than 7 times, through sustained, rapid economic growth.

This is blatantly false. Our initial economic booms were due to labor exploitation (child labor, poor working conditions, no minimum wage, etc.) and the military industrial complex. Secondly, if you look at the tax rates through the 50s and 60s, some of the argueably better economics years of the 20th century, you will see that what Farrara is arguing about tax is completely contrairy to the actual statistics (which, at the very least suggests that there is no causitive relationship between tax rates and economic health, and at the best suggests that high taxes that essentially scale with your income are causitive to the economy's health. In reality, it suggests something in between). For example, take these statistics of incomes adjusted for inflation vs marginal tax rates[2]: in 1960, a single person making $1,163,483 dollars was taxed at the rate of 90% and a head of house making $100,000 was taxed at 36%.

But President Obama’s tax policy of increasing all tax rates on savings and investment will work exactly contrary to such economic growth.  It is savings and investment which creates jobs and increases productivity and wages.  Under capitalism, capital and labor are complementary

These are unsubstantiated assertions. He gives no reason why I should believe what he says.

Anyways, I must admit, I don't have the energy to persist in my writing. I'm tired and still have homework to do (which involves much, much denser, drier reading than that of Farrara's… :)). I'll just conclude in saying that although there are some claims that Farrara makes that seem to be substantiated (however, I'm skeptical that real substantiation can be provided in a Forbes article), the large majority of his claims aren't sufficiently (or at all) substantiated. For that reason alone, I would take everything that this man writes in such Forbes-like articles with a grain of salt.


[1] Think about the value of $50 to someone making minimum wage to a multi-millionaire or billionaire. If each person respectively were to lose a $50 bill, the so decrease in so called "opportunity cost" between the two is hugely different (i.e. A minimum wage worker will "get a lot more" out of that $50 bill). Ideally "fairness" needs to be judged upon an adjusted scale of relative value.

[2] http://taxfoundation.org/article/us-federal-individual-income-tax-rates-history-1913-2013-nominal-and-inflation-adjusted-brackets

In Good Company

Regarding my last post, I'm glad to see I'm in good company in feeling that object-oriented programming is not the be-all, end-all to software design (nor is it always a good design). Now if only I could get my school's Software Engineering department to agree...

I should also note, I have a lot more to my opinion than what I crudely wrote in my last post. I just don't feel particularly motivated to expand upon them because religion is religion is religion and I doubt anyone reading this (if there is anyone reading this) will alter their views based on what I have to say.