{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **Note** \n",
    "* All items of problems in problem sets should be done in seperate cells.\n",
    "* Do not forget to include title, labels of each line and set axis names for every figure you plot.\n",
    "* You can submit incomplete problems. They will be graded as well.\n",
    "* Bonus tasks are challenging and non-obligatory. However, they may help you with your final grade."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 1 (Python demo: convolution of a signal)\n",
    "## 40 pts\n",
    "\n",
    "* First of all download one of the $\\verb|.wav|$ files with starcraft sounds from [here](https://github.com/oseledets/nla2015/tree/master/lectures). Load them in python and play using functions from [lecture 1](../lectures/bss1.ipynb).\n",
    "\n",
    "Our next goal is to process this signal by multiplying it by a special type of matrix (convolution operation) that will smooth the signal. \n",
    "\n",
    "* Before processing this file let us estimate what size of matrix we can afford. Let $N$ be the size of the signal. Estimate analytically memory in megabytes required to store dense square matrix of size $N\\times N$ to fit in your operation memory. Cut the signal so that you will not have swap (overflow of the operation memory).\n",
    "\n",
    "\n",
    "* Create matrix $T$: $$T_{ij} = \\sqrt{\\frac{\\alpha}{\\pi}}e^{-\\alpha (i-j)^2}, \\quad \\alpha = \\frac{1}{20}, \\quad i,j=1,\\dots,N.$$ Avoid using loops or lists! The function [scipy.linalg.toeplitz](http://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.linalg.toeplitz.html) might be helpful for this task.\n",
    "**Note:** matrices that depend only on difference of indices: $T_{ij} \\equiv T_{i-j}$ are called **Toeplitz**. Toeplitz matrix-by-vector multiplication is called **convolution**.\n",
    "\n",
    "\n",
    "* Multiply matrix $T$ by your signal (for matvec operations use $\\verb|numpy|$ package). Plot first $100$ points of the result and first $100$ points of your signal on the same figure. Do the same plots for $\\alpha = \\frac{1}{5}$, $\\alpha = \\frac{1}{100}$ using subplots in matplotlib. Make sure that you got results that look like slighly smoothed initial signal.\n",
    "\n",
    "\n",
    "* Play the resulting signal. In order to do so format your array into $\\verb|int16|$ before playing by using\n",
    "```python\n",
    "your_array = your_array.astype(np.int16)\n",
    "```\n",
    "\n",
    "\n",
    "* Measure times of multiplications by $T$ for different values of $N$ and plot them in loglog scale. What is the slope of this line? Why?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2 (Instability of the standard Gram-Schmidt algorithm)\n",
    "\n",
    "## 30 pts\n",
    "Our goal now is to orthogonalize a system of linearly independent vectors $v_1,\\dots,v_n$.\n",
    "The standard algorithm for the task is the Gram-Schmidt algorithm:\n",
    "$$\n",
    "\\begin{split}\n",
    "u_1 &= v_1, \\\\\n",
    "u_2 &= v_2 - \\frac{(v_2, u_1)}{(u_1, u_1)} u_1, \\\\\n",
    "u_3 &= v_3 - \\frac{(v_3, u_1)}{(u_1, u_1)} u_1 - \\frac{(v_3, u_2)}{(u_2, u_2)} u_2, \\\\\n",
    "\\dots \\\\\n",
    "u_n &= v_n - \\frac{(v_n, u_1)}{(u_1, u_1)} u_1 - \\frac{(v_n, u_2)}{(u_2, u_2)} u_2 - \\dots - \\frac{(v_n, u_{n-1})}{(u_{n-1}, u_{n-1})} u_{n-1}.\n",
    "\\end{split}\n",
    "$$\n",
    "Now $u_1, \\dots, u_n$ are orthogonal vectors in exact arithmetics. Then to get orthonormal system you should divide each of the vectors by its norm: $u_i := u_i/\\|u_i\\|$.\n",
    "\n",
    "* Implement the described Gram-Schmidt algorithm and check it on a random $10\\times 10$ matrix. **Note:** To check orthogonality calculate the matrix of scalar products $G_{ij} = (u_i, u_j)$ (called Gram matrix) which should be equal to the identity matrix $I$. Error $\\|G - I\\|$ will show you how far is the system $u_i$ from orthonormal.\n",
    "\n",
    "\n",
    "* Create a Hilbert matrix of size $10\\times 10$ without using loops.\n",
    "\n",
    "\n",
    "* Othogonalize its columns by the described Gram-Schmidt algorithm. Is the Gram matrix close to the identity matrix in this case? How do you think why?\n",
    "\n",
    "The oberved loss of orthogonality is a problem of this particular algorithm. To avoid it [modified Gram-Schmidt algorithm](https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Numerical_stability) can be used. Moreover we will talk about more advanced algorithms later (QR decomposition lecture)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 3 (Unitary invariance of norms)\n",
    "\n",
    "## 30 pts\n",
    "\n",
    "One of the key properties of norms that will help us to work easily with singular value decomposition (one of the key concepts of this course; will be discussed later) is unitary invariance of second, spectral and Frobenius norms.\n",
    "Let us prove them.\n",
    "\n",
    "* Prove that the second vector norm $\\|\\cdot\\|_2$ is unitary invariant: for any unitary matrix $U$ and any vector $x$ holds $\\|Ux\\|_2 = \\|x\\|_2$\n",
    "\n",
    "\n",
    "* Prove that the spectral matrix norm $\\|\\cdot\\|_2$ is unitary invariant: for any unitary matrices $U$ and $V$ and for any matrix $A$ holds $\\|UAV\\|_2 \\equiv \\|A\\|_2$. **Hint:** use definition of the operator norm\n",
    "\n",
    "\n",
    "* In order to prove unitary invariance of the Frobenius norm prove first that $\\|A\\|^2_F = \\text{trace}(AA^*) = \\text{trace}(A^*A)$\n",
    "\n",
    "\n",
    "* Now prove that the Frobenius norm is unitary invariant. You can use the following property of the trace: $\\text{trace}(BC) \\equiv \\text{trace}(CB)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 4 (Bonus)\n",
    "\n",
    "* Given $A = [a_{ij}] \\in\\mathbb{C}^{n\\times m}$ prove that for operator matrix norms $\\Vert \\cdot \\Vert_{1}$, $\\Vert \\cdot \\Vert_{\\infty}$ hold\n",
    "$$ \\Vert A \\Vert_{1} = \\max_{1\\leqslant j \\leqslant m} \\sum_{i=1}^n |a_{ij}|, \\quad \\Vert A \\Vert_{\\infty} = \\max_{1\\leqslant i \\leqslant n} \\sum_{j=1}^m |a_{ij}|.$$\n",
    "\n",
    "* The norm is called absolute if $\\|x\\|=\\| \\lvert x \\lvert \\|$ holds for any vector $x$, where $x=(x_1,\\dots,x_n)^T$ and $\\lvert x \\lvert = (\\lvert x_1 \\lvert,\\dots, \\lvert x_n \\lvert)^T$. Give an example of a norm which is not absolute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}