Continuing last post, we will resume talking about matrix completion in this. As the title suggests, these are some basic facts about the problem so I’ll provide some interesting references at the end.

# Category Archives: Mathematical

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

# Some basics

OK, this post is supposed to be a gentle introduction to some of the words or terminologies used in math. What is a ‘set’? A set is a collection of distinct objects, eg: {apple, orange}, {football, basketball} etc.. As we can see, a set is written with ‘{‘, ‘}’ brackets, the examples are read as ‘a set of (or consisting of) apple and orange’ and so on. Individual entities of a set are called as ‘elements’ simply because they make up the set that we are interested in. As we can see, we can’t do much just with a set, well it’s not true cause lots of interesting objects are almost always defined using a set, but anyway what we really care about is ‘relations’ and ‘mappings’.

# Linearity – I

The word ‘linear’ is used in so many different contexts that it kind of loses its importance. After a lot of contemplation, it turns out that this word as simple as it may sound, has far reaching consequences. The point of this post is to exactly make this clear and precise (maybe not precise). There are lots of ways to describe linearity. Someone who has taken a calculus course in high school or college will say that things are nice when everything is linear, for example linear equations or straight lines have a constant slope, oops we need to define what ‘slope’ is. Let’s say we would like to buy sugar. The cost of a kilogram of sugar is $10 and to simplify things, we pay a tax of $5 how much ever the quantity is. If we want to buy 10 kilograms of sugar, we need $105 i.e., 10 times 10 plus 5(meh). A linear equation is a thing that can be written in this form i.e., c = ax + b where a and b can be any arbitrary numbers, x is the amount of sugar and c is the total cost to buy x kilograms of sugar. The number a is often called as the slope since it decides how steep the function, that is, if a is a big positive number then we can say that the buying sugar will be expensive and so on, well to be honest it also depends on b but let’s say that we always have $b. We note at this point that this also allows a to be zero (now what does that mean in our example? I’ll leave that for you). But the situation is bad when a is zero, why? this requires some amount of reasoning and some machinery or terminology to address this issue.