The State of Being Stuck — Math with Bad Drawings

Advice from a guy who spent a decade on a single math problem.

via The State of Being Stuck — Math with Bad Drawings

Advertisements

Optimization in Life

I’ve been doing a lot of optimization related work and courses, for my PhD, most notably in convex optimization and non-linear programming. They say that the best way to learn theory is to implement it in real life, and so I thought that it wouldn’t hurt to find ways to optimize… life… eh? On that optimistic enough thought, here we go:

  1. The steepest descent is not necessarily the fastest. A common thing that people do when they are in an unwanted situation is to do starkly opposite of what they were initially doing, i.e. -\nabla f(x). This seems to be a go-to solution for minimizing conflict. However, it is well known that to reach the point of minimum (conflict), steepest descent can take far more number of iterations than other gradient based methods. So take it easier, guys. Extremeness is not a smart option.
  2. When bogged down by multiple issues, solve one-problem at-a-time. Coordinate descent is an approach in which the objective (life’s problems) is minimized w.r.t a fixed coordinate at a time. It’s known for its simplicity of implementation.
  3. The apple does not fall far from the tree. So when Newton came up with his method for optimizing functions, the initial estimates did not fall far from the optimum, most notably in the case of quadratic functions. Turns out, it helps to approximate functions at each point with quadratic estimates, and then to minimize that quadratic estimate. Basically, take a problem and convert it into an easier sub-problem that has a known minimum. Move on to the next sub-problem. This fetches you the global optimum much faster.
  4. While positive definiteness is ideal, positive semi-definiteness is good too. If the Hessian of the function to be minimized is positive semi-definite, then the function is convex and can be minimized easily (its local optimum is the global optimum). So keep calm (and kinda positive) and minimize issues.
  5. Often when there are too many parameters to handle, we tend to overfit a fairly complicated model to our life. In such cases, it is a good idea to penalize over-complication by adding a regularization term. Regularization also helps in solving an ill-posed problem. If we tend to focus on only a specific set of problems, we forget other facets of life, which leads us into making poorer choices. The key is to find the right balance or trade-off.
  6. Some problems actually have closed-form or unique solutions. There’s just one possible answer which is apparent enough. In that scenario the optimal strategy should be to stop optimizing. Stop contemplating, just go-get-it!
  7. On a closing note, heuristically speaking, one would need to try out a bunch of optimizing techniques to find the optimal optimization technique.
optimization

XKCD

To make this post even more meta, how optimal would it be if the moral of this post converged to this statement?

Signal Measurements: From linear to non-linear

The best kind of problems to solve are linear measurements

y = Ax

where A is a square matrix, and essentially requires linear programming (or simple matrix calculations).

minimize  c

subject to  Ax = y

which equivalently, has the closed form solution given by

x = A^{-1} y.

If A is full rank and square, we have a unique solution that satisfies a one-one mapping between inputs x_i and outputs y_i. If we go slightly out of comfort zone, we come to the easiest class of nonlinear programming, for linear measurements, which is convex optimization. Why? Because in convex functions, local optimum is global optimum. They are nice that way: as long as you can ensure that with each iteration, you are reducing your objective value, at an appropriate enough rate, you will converge to the correct solution.

An example of this type of problem is still y=Ax, with A being a tall matrix, which can be formulated as a least-squares problem. If A is full rank, it has a unique solution that can be computed using a matrix pseudo-inverse. (Note: In this model, there is no one-one mapping between x_i‘s and y_i‘s. There are more equations than variables, which means we may not be able to find a set of x_i‘s which satisfy all of the equations. We can however find an x  which comes close enough to the measurements, by minimizing the deviation of the measurement model from the actual measurements).

minimize  \|Ax-y\|^2_2

which equivalently, has the closed form solution given by

x = (A^TA)^{-1} A^Ty.

What about linear-measurement models that are inherently non-convex? Consider A to be a fat matrix, we can have infinitely many solutions (A is rank deficient). We further impose a restriction on x to be k-sparse (of course, this imposition is natural enough. We are collecting less information about our signal than we’re supposed to. If we want to uniquely recover the signal, we need to utilize certain properties about the structure of the signal). The problem is called the compressed sensing problem, and can be stated as

minimize \|y-Ax\|_2

subject to \|x\|_0 \leq k.

This problem is np-hard to solve. However, if we choose A such that it satisfies restricted isometry property depending on parameter k, then we can still uniquely recover x, using convex optimization. Of course there are non-convex approaches as well, but a common convex approximation is the lasso problem

minimize  \|Ax-y\|^2_2 + \lambda \|x\|_1.

This is harder than our vanilla least-squares formulation, but still, very much in the realms of the well established convex optimization algorithms. Now let’s get even more out of our comfort zone. Non-linear problems that are non-convex. So we come to phase retrieval

y = |Ax|

which is equivalent to

y_j = |a_j^T x| for j=1,2\dots m

or

y_j = (a_j^T x)^2 .

Insane! Phase contains most of the information! As you might have noticed the trend, we’re trying to recover more using lesser and lesser information. A common analysis suggests that most of the information about a signal is contained in the phase of the measurements, not the magnitudes.

Now this function is highly non convex. Why? For convex functions all sub-level sets are convex. What that means is, take a convex curve. Think parabola symmetric about y axis. And now cut it with y = t , for any t, and look at the part of the parabola that lies below y=t ( y-axis is f(x)). We want to look at all x such that f(x) < t, for any t. It just forms a line segment on the x-axis. Now a line segment is a convex set. This parabola hence has a unique minimum.

Now think of a highly irregular curve with say 5-6 local minima, 5-6 global maxima and 1 global minimum. Such curves are not convex, because when you project them on to the x-axis, they don’t form convex sets.

Of course, we then resort to using the first trick from our new signal processing handbook. Make things linear and convex. A clever way to look at

y = |Ax|.

is to “linearize” it .

y_{ph} = phase(Ax)

then

y \circ y_{ph} = Ax

where were looking at an element-wise product, on the left side. This can be better written as

Cy = Ax

where C is a diagonal matrix C = diag(y_{ph}). And so the problem turns into

minimize over x,C\quad\|Ax-Cy\|_2.

It’s easy to see that this problem is not convex. Because the entries of diagonal of C are restricted to be phase values. They have to have unit magnitude. This isn’t a convex set. So now what do we do ?

What AltMinPhase does is that it looks at it as 2 alternating minimizations with C and x being variables. For constant C, this is convex and is a least-square problem if A is full rank. For constant x, it is easy to see that the optimal C is given by

C = phase( y_{apparent}) = phase(Ax).

They then alternatively, minimise over these 2 variables. Now think back to the highly non-convex function with multiple local minima and maxima. If you initialize wrongly, you’re very likely to hit a local minimum. And that’s the end of it. Wrong solution!

Initialize correctly, close enough to the global minimum (which should ideally be very close to the true x = x^*, for a noiseless case), and bam! It’s a very fast convergence algorithm. If A is iid Gaussian, we can design an initial vector which has an expected value equal to the true value x^*. Beauty of random matrix theory (the same thing that helped us solve the compressed sensing problem).

*******

In the next few posts, I will write about the intuition and big picture of some of the current topics in signal processing, like structured sparsity, phase retrieval, random matrix theory and some applications in machine learning. In doing so, I hope to create a good database of ideas related to my research.

The Physics of Interpersonal Relationships

1. Frictional force is directly proportional to normal reaction force between two people. If the two entities are close to each other, and at opposition, the more reaction supplied by either parties, the more friction. Also, work done by frictional force is non conservative in nature. One can only expend more and more time and energy into bickering with the other party, without expecting equivalent valuable output. Much is lost as heat.

2. Gravitational force is inversely proportional to the square of the physical distance between two people. If you find yourself gravitating towards someone, when you shouldn’t be, maintain a physical separation of at least 15 ft. That minimizes chance of physical contact and any form of non-awkward conversation.

3. If you find yourself fast accelerating into an unwanted situation with someone, the only way to change course of the events is to apply a jerk. Change in acceleration can be characterized by either one entity or favorably both being jerks.

4. The first law of thermodynamics states that energy of an isolated system is constant. One may decide to channel their energies into productive work and recreational hobbies, or indulge in interpersonal warfare, but not both. I’d pick the first.

5. Neural pathways get trained based on the associations between input stimulus to the output reaction. The weights on these pathways can be adjusted by experimentally varying the reactions to specific stimuli. If you dislike someone, for eg. a woman in your workplace that completely cold shoulders you even when you are sweet to her and offer sage advice on where to get the best kind of food in the locality, and giving her a heads up in the time of need, your most natural reaction is to detest that woman. You feel insulted. Now replace this feeling with that of pity for the poor woman who can’t see right from wrong.

Some associations might be tagged as positive compulsions. For example, when you feel disappointed by the lack of people to talk to, start writing a blog post instead. Wink wink.

6. Newton’s law of cooling suggests that rate of cooling is proportional to difference in temperature of the body and its surroundings. If you find yourself constantly agitated by your surroundings, walk out of the room. Staying in the room will only maintain or increase your agitation.

7. If two people have a charged discussion and are speeding through an argument, then in the presence of a magnetic field, they’re likely to experience a perpendicular force, called the Lorentz force, most likely in the form of a slap or punch, not by Lorentz himself.

8. If two interacting people have the same wavelength, a slight change in wavelength causes the formation of beats. A pattern of constructive and destructive interferences follows. In that case, just listen to the beat of your own music, some sound logic will follow.

Time Dilation

If you had a choice, would you speed through life or would you rather have time stand still?

Of course, any change in the perception of time would deal with three things:

1. Traveling at speeds close to speed of light. Relativistic effects.

2. Changing how your neurons perceive light, sound and other stimuli that model time. Zeitgebers.

3. Changing external stimuli in ways that trick your brain into perceiving time differently.

Now, I’ll rule out 1, though my inner physicist might love to get back to it at some point in the future. Points 2 and 3 are equally interesting.

Point 2 has much to do with the rate with which your brain perceives new information, and what weight it gives to that new piece of information. I watched a video on Stoner sloth today that sparked this thought process. Smoking cannabis has an effect of slowing down the perception of time. Smokers tend to react slowly to external stimuli, and hence like a sloth. Now, I haven’t ever smoked weed, nor do I wish to, but I do wonder about the cognitive process that goes into this phenomenon. I suppose the neural pathways linked to visual and auditory stimuli are activated a lot more than other senses, which possibly leads to an information overload on them. There’s a also a sense of hyperfocusing. The intensity with which you sense your surroundings, is high, much like during meditation. There’s also an associated thought jumping. The mind makes associative thoughts quite quickly and abruptly, which leads the user to believe that a huge stream of thoughts have passed the mind in a less time, giving the perception of an elongated time frame.

Point 3 is something I read about two days back, on virtual reality using oculus rift, source: IEEE Xplore. They’ve set up a cool experiment in which they divide people into three sets, formulating three different visual stimuli, using three different test conditions. For all three sets, the basic scene was the same; a beach side with a setting sun. In the second and third sets, they introduced verbal and spatial tasks, by flashing letters and mobile objects, respectively. The three different test conditions were: a stationary sun, a realistically setting sun, a sun setting twice as fast.

Due to lack of any other stimulus, the people in set 1 overestimated time, and were hugely affected by the setting time of the sun, in estimating the length of time spent.

Meanwhile people in sets 2 and 3 under estimated the passage of time, due to their brains being involved in several cognitive tasks. They were also relatively less affected by the setting time of the sun.

While this experiment serves as a good lesson in virtual reality, it does make me wonder, if we will be able to simulate conditions that would, say make us more productive by giving the illusion of time flying. Or slowing time down if we feel overwhelmed by the cascade of things happening in our lives. I guess only time will tell?

Image source: comvita.com

Quantum Superpositions of Life. Or not.

2536428

For everyone familiar with the quantum superposition principal (or have heard the folklore of a cat owned by a certain Schrodinger), the state of a quantum system is determined by the superposition of square-rooted probabilities of all possible states that the system can take. Practically speaking your future is

\sqrt{\alpha}*\left|bright\right\rangle + \sqrt{1-\alpha}*\left|bleak\right\rangle

where 0 < \alpha < 1 and \left|bright\right\rangle \:\:and\:\: \left|bleak\right\rangle are orthonormal states.

While there is no inherent ‘quantumness’ to this scenario, it still obeys a superposition principal, except that \alpha is undetermined. It however, is not impossible to fit a probabilistic model into this framework, based on past experiences.

The brightness or bleakness of the future gets determined, when one gets to the future (or in other words, performs a direct measurement of the system). It’s the same with a quantum system. The superposition collapses once a measurement is performed.

What I’m trying to say is that, the superposition principle isn’t unique to the quantum world. However, what physicists take advantage of, in quantum systems, is retaining the super-imposibility of the system. The idea is to perform a series of operations on a superimposed system, that does not at any point destroy the superposition, and to take advantage of the fact that the value of \alpha is known.

For instance, one may seek to turn tables. In which case, one applies a NOT gate, which happens to be a Pauli X matrix.

X*(\sqrt{\alpha}*\left|bright\right\rangle + \sqrt{1-\alpha}*\left|bleak\right\rangle ) = \sqrt{\alpha}*\left|bleak\right\rangle + \sqrt{1-\alpha}*\left|bright\right\rangle .


The idea of teleportation has forever fascinated mankind, and somehow people believe that if quantum teleportation is possible, an equivalent human form will exist some day. However, the idea behind teleportation, even in the quantum world, pertains to teleportation of information, not the particle itself. So while it might entail faster that light communication, it does not validate the simultaneous disappearance and reappearance of the qubit. This is where the ‘quantumness’ comes to play, due to a concept called quantum ‘entanglement’, that I shall discuss in the next post. Probably.

What is this blog all about?

What can you expect from this blog? Articles about science, philosophy and psychology? The philosophy behind scientific psychology!

Writing this blog, is basically a way of arranging the pseudo-scientific thoughts that come to my mind in a more coherent fashion which may boggle the minds of the fellow readers, but also aims to ignite a discussion.

Topics of my interest range from physics to science fiction to the realms of life. I also like analyzing signals. Both the experimental and the mental kind.

Needless to say, I like playing with words. I don’t just play, I cavort with them. I use so many euphemisms at times,  it’s not even punny.

I love dwelling on inconclusive problems. More than that, I love analyzing solutions. I also like pretending to know-it-all. At least there’s no pretension about that.

So what does this all result in? Ramblings of an 20-something self-proclaimed nerdy woman on a virtual canvas that is this blog. Quod erit demonstrandum.