# Author Archives: Sathya

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

# Bare bones of Matrix Completion – I (7 mins read)

This last three weeks I was in Utah for a summer math school or conference whichever you prefer that was organized by the Institute of Advanced Studies (IAS), Princeton, New Jersey. Basically we had three weeks of lectures, problem sessions, endless fun discussions day in day out with free food, free stay – the resort was amazing, we stayed at the Zermatt resort (if you’re using headphones you might wanna turn the volume down a bit). Anyway, the point of this post is lectures given by Roman Vershynin that I sat through on Random Matrices and applications (basically this is a scribe). Specifically, about the famous problem called as matrix completion. Later (hopefully soon) I’ll write about another topic that definitely got my attention called as Differential Privacy.

# 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?