IIT M FOUNDATION FN EXAM QDF1 13 Apr - 13 Apr 2025

Concepts this paper tests

Auto-generated summary from the source site. Handy as a checklist; the lessons above explain each idea from scratch.

Here’s a structured summary of core topics, concepts, principles, and equations essential for the exam, followed by Mermaid knowledge graphs to visualize relationships.

1. Core Topics & Key Concepts

A. Probability & Statistics

1. Joint Probability Density Functions (PDFs) & Transformations

• Key Idea: Transform random variables $(X, Y)$ to new variables $(U, V) = (X+Y, X-Y)$ and derive the joint PDF of $(U, V)$.

• Steps:

  1. Find the Jacobian determinant $J$ of the transformation.
  2. Express $f_{U,V}(u,v) = f_{X,Y}(x(u,v), y(u,v)) \cdot |J|$.
  3. Define the support region for $(U, V)$.
• Equation:

For $U = X + Y$, $V = X - Y$:

Thus:

Support: $|v| \leq u \leq 4 - |v|$, $-2 \leq v \leq 2$.

2. Expected Value & Linearity

• Key Idea: For independent RVs $X_1, X_2, X_3$, $E[X_1 + X_2 + X_3] = E[X_1] + E[X_2] + E[X_3]$.

• Distributions & Expectations:

  • Uniform(0,1): $E[X_1] = 0.5$
  • Poisson(λ=3): $E[X_2] = 3$
  • Exponential(λ=2): $E[X_3] = \frac{1}{2}$
  • Total: $E[S] = 0.5 + 3 + 0.5 = 4$.

3. Markov’s Inequality

• Key Idea: Provides an upper bound for the probability that a non-negative RV exceeds a threshold.
• Equation:

Example: $P(X \geq 16) \leq \frac{8}{16} = 0.5$.

4. Cumulative Distribution Function (CDF)

• Key Idea: For Uniform(0,4), $F_X(x) = \frac{x}{4}$ for $0 \leq x \leq 4$.
• Example: $F_X(2) = \frac{2}{4} = 0.5$.

B. Linear Algebra & Matrix Decompositions

1. Singular Value Decomposition (SVD)

• Key Idea: Decomposes a matrix $A$ into $A = U \Sigma V^T$, where:

  • $U$: Left singular vectors (eigenvectors of $AA^T$).
  • $\Sigma$: Diagonal matrix of singular values (square roots of eigenvalues of $A^T A$).
  • $V$: Right singular vectors (eigenvectors of $A^T A$).

• Properties:

  • Rank of $A$ = Number of non-zero singular values.
  • SVD is not unique for square matrices (depends on sign flips in $U$ and $V$).

2. Principal Component Analysis (PCA)

• Key Idea: Projects data onto a lower-dimensional subspace capturing maximum variance.

• Steps:

  1. Compute the covariance matrix $\Sigma$.
  2. Find eigenvectors (principal components) and eigenvalues (variances).
  3. Sort eigenvectors by descending eigenvalues.

• Properties:

  • Principal components are orthogonal and uncorrelated.
  • Directions of maximum variance = eigenvectors of $\Sigma$.

C. Optimization

1. Convexity

• Convex Functions:

  • Definition: $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$ for $\lambda \in [0,1]$.

  • Examples:

    • Convex: $e^{x+2}$, $x^2$, $x^4 - 4x^2 + 5$ (globally convex if $f''(x) \geq 0$).
    • Non-convex: $\ln x$, $\sin x$.
  • Second Derivative Test: $f''(x) \geq 0$ implies convexity.

• Convex Sets:

  • Definition: $\lambda x + (1-\lambda)y \in S$ for all $x, y \in S$.

  • Examples:

    • Convex: Lines, intersections of convex sets.
    • Non-convex: Arbitrary curves.

2. Gradient Descent

• Key Idea: Iteratively minimize a function $f$ using the gradient $\nabla f$.
• Update Rule:

Example: For $f(x,y) = x^2 + 3y^2 -4x +6y$, $\nabla f = (2x-4, 6y+6)$. At $(2, -1)$, $\nabla f = (0, 0)$, so no update occurs.

3. Karush-Kuhn-Tucker (KKT) Conditions

• Key Idea: Necessary conditions for optimality in constrained optimization.

• Conditions:

  1. Stationarity: $\nabla L = 0$ (Lagrangian gradient).
  2. Primal Feasibility: Constraints satisfied.
  3. Dual Feasibility: Lagrange multipliers $\alpha, \beta$ satisfy sign constraints.
  4. Complementary Slackness: $\beta (w - \delta) = 0$.

• Example: For $\min x^2 + y^2 + z^2 + w^2 + 1$ s.t. $x+y+z+w=1$, $w \leq \delta$:

  • $x = y = z = \frac{\alpha}{2}$, $w = \alpha - \beta$.
  • If $\delta > \frac{1}{4}$, $w = \frac{1}{4}$, so $x = \frac{1}{4}$.

D. Calculus & Function Analysis

1. Critical Points & Extrema

• Key Idea: Find minima/maxima by solving $f'(x) = 0$ and checking the second derivative.

• Example: For $f(x) = x^4 - 4x^2 + 5$:

  • Critical points: $x = 0, \pm \sqrt{2}$.

  • $f''(x) = 12x^2 - 8$.

    • $x = 0$: $f''(0) = -8$ (local maxima).
    • $x = \pm \sqrt{2}$: $f''(\sqrt{2}) = 16 > 0$ (local minima).

Graph 2: Linear Algebra & PCA

Graph 3: Optimization & Convexity

Graph 4: Calculus & Extrema