# Category Archives: Uncategorized

Alright before we start, I’m gonna call the Conditional Gradient Algorithm as Frank-Wolfe Algorithm (FW), attributing to the authors of the first ever paper on these methods viz., Marguerite Frank and Philip Wolfe in 1956!  The simplex method (one of the top 10 algorithms of the 20th century, I’d say that simplex gets the first place for me) was introduced by Dantzig (I strongly encourage to read the history in the wiki page, it’s amazing!) in 1947 for solving linear optimization (LO) problems. A LO algorithm solves the following question: Let’s say we are given with the following two types of data viz., 1. A linear function $f$ in say $\mathbb{R}^n$; 2. Legal set: A (sub)set of points $C\subseteq \mathbb{R}^n$ that can described just using linear equations or inequalities. Now how can I pick the point in the legal set $C$ where $f$ achieves the minimum value (or maximum value, it doesn’t matter in this case only, in general this is not true).

# Bare bones of Matrix Completion – III (4 mins read)

This will  hopefully the last post in the matrix completion problems. But since the MBI inequality is widely used, I decided to squeeze in one more application of Community Detection problem in this as well (yay!) in the future post. So first the matrix completion. problem, we will see how a simple algorithm can yield exact results. To that end, since the problem as stated is ill posed, we will first make some assumptions on the matrix that we are completing, namely, the low rank assumption (we will discuss the case where the matrix we are completing is square).

# Why are vector spaces so good

In the basics we saw that vector spaces (v.s.) are defined over a field. Field is the keyword. Recall that examples of field include real numbers ‘r’, complex numbers ‘c’, rational numbers ‘q’. Let’s take the last example of q. q consists of numbers of the form a/b where a and b are integers like -2, 3, 5, 10 etc.. Examples of numbers that are not rational include square root of 2, pi, e etc.. v.s. of dimension n are sets of n – tuple of numbers where each number in the tuple comes from the underlying field. The question is, why do we need a field, that is, why can’t we just define it over the set of integers ‘z’. Recall also that z shares all properties with q except that not all elements have a multiplicative inverse i.e., there is no number for 21 in z so that the product of both of these numbers equal 1 but if we ask for an element in q, then we have 1/21 * 21 = 1. But that’s ok because nothing is stopping me from defining n – tuples from z. For example let’s look at z^2 which consists of numbers of the form (a,b) where a and b are integers. Well, the world didn’t come to an end anyway, in fact, we can see that if we take two 2- tuples of this form and add them coordinate-wise, we get a number of the same form with different integers. Secondly, if we multiply (coordinate-wise) a 2-tuple with an integer we still end with a different 2-tuple where each coordinate is again an integer, so what’s the problem?

If you noticed, a significant of aspect this blog is digression all over so I thought it is only natural for me to write about it. It turns out that one of the main reasons why math is ‘hard’ for those who feel that it is hard is that they learn math the hard way which is why it is hard. That doesn’t obviously sound like a thing, but the truth is that it is as good as any other reason. Let’s take an example.