{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ordered-morocco",
   "metadata": {},
   "source": [
    "Given the matrix $\\mathbf\\Phi$ defined by"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "funny-genome",
   "metadata": {},
   "source": [
    "$\\mathbf\\Phi(\\mathbf x, M) =\n",
    "\\begin{bmatrix}\n",
    "    (x_0)^0 & (x_0)^1 & \\cdots & (x_0)^{M - 1} \\\\\n",
    "    (x_1)^0 & (x_1)^1 & \\cdots & (x_1)^{M - 1} \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    (x_{N - 1})^0 & (x_{N - 1})^1 & \\cdots & (x_{N - 1})^{M - 1}\n",
    "\\end{bmatrix}\n",
    "\\qquad \\mathbf x \\in \\mathbb{R}^N \\qquad M \\in \\mathbb{N} \\qquad \\mathbf\\Phi(\\mathbf x, M) \\in \\mathbb{R}^{N x M}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "urban-texture",
   "metadata": {},
   "source": [
    "implement a function in python using numpy which computes $\\mathbf\\Phi(\\mathbf x, M)$ without the use of `for` loops."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "collectible-literacy",
   "metadata": {},
   "source": [
    "To do so, note that\n",
    "\n",
    "$\\mathbf\\Phi(\\mathbf x, M) = \\mathbf A \\hspace{0.2em} \\hat\\diamond \\hspace{0.2em} \\mathbf B$\n",
    "$\\qquad \\mathbf A =\\begin{bmatrix}\n",
    "    x_0 & x_0 & \\cdots & x_0 \\\\\n",
    "    x_1 & x_1 & \\cdots & x_1 \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    x_{N - 1} & x_{N - 1} & \\cdots & x_{N - 1}\n",
    "\\end{bmatrix}\n",
    "\\qquad \\mathbf B = \\begin{bmatrix}\n",
    "    0 & 1 & \\cdots & M - 1 \\\\\n",
    "    0 & 1 & \\cdots & M - 1 \\\\\n",
    "    \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "    0 & 1 & \\cdots & M - 1\n",
    "\\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "figured-scoop",
   "metadata": {},
   "source": [
    "where $\\hat\\diamond$ denotes element wise exponentiation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cloudy-athletics",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "recorded-female",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Reference implementation with for loops\n",
    "def phi(x, M):\n",
    "    phi = np.zeros((x.size, M))\n",
    "    for n in range(x.size):\n",
    "        for m in range(M):\n",
    "            phi[n, m] = x[n]**m\n",
    "    return phi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "macro-jamaica",
   "metadata": {},
   "outputs": [],
   "source": [
    "phi(10 * np.arange(4), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "furnished-index",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using elementwise exponentiation of arrays that have the same shape, wastes time and memory on copies\n",
    "def phi(x, M):\n",
    "    A = np.repeat(x.reshape(x.size, 1), M, axis = 1)\n",
    "    B = np.repeat(np.arange(M).reshape(1, M), x.size, axis = 0)\n",
    "    return np.power(A, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "japanese-setting",
   "metadata": {},
   "outputs": [],
   "source": [
    "phi(10 * np.arange(4), 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "finite-jesus",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Using elementwise exponentiation with broadcasting\n",
    "def phi(x, M):\n",
    "    return np.power(x.reshape(x.size, 1), np.arange(M).reshape(1, M))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "liberal-community",
   "metadata": {},
   "outputs": [],
   "source": [
    "phi(10 * np.arange(4), 3)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}