Algorithms for Data Science · Quiz 2 · May 2025

**Step 1: Apply Markov's Inequality to the non-negative random variable \(D = \|X\| \ge 0\).** We are given that the mean distance of \(X\) from the origin is \(\mathbb{E}[D] = 10\). By Markov's inequality: \[P(D > 50) \le \frac{\mathbb{E}[D]}{50} = \frac{10}{50} = 0.2\] **Step 2: Bound \(p = P(D \le 50)\).** \[p = 1 - P(D > 50) \ge 1 - 0.2 = 0.8\] **Answer: A (\(p \ge 0.8\))** A: **Correct:** By Markov's inequality, \(P(\|X\| > 50) \le 10/50 = 0.2\), so \(p = P(\|X\| \le 50) \ge 0.8\). B: **Incorrect:** Reverses the inequality direction from Markov's inequality. C: **Incorrect:** \(p \ge 0.2\) is not the tightest bound since \(p \ge 0.8\) holds. D: **Incorrect:** \(0.2\) is the upper bound on the tail probability \(P(\|X\| > 50)\), not \(P(\|X\| \le 50)\).

According to the **Johnson-Lindenstrauss (JL) Lemma**, the required lower-dimensional embedding dimension \(k = O\left(\frac{\ln n}{\epsilon^2}\right)\) depends **only** on the number of data points \(n\) and the distortion parameter \(\epsilon\)—it is completely **independent** of the original ambient dimension \(d\). Since datasets \(D_1\) and \(D_2\) have the same number of data points \(n\) and use the same \(\epsilon = 0.01\), \(k_1\) and \(k_2\) **can be chosen to be equal to each other** regardless of \(d_1 / d_2 = 1000\). **Answer: D (\(k_1\) and \(k_2\) can be chosen to be equal to each other)** A: **Incorrect:** The target dimension \(k\) in the JL lemma does not depend on the ambient dimension \(d_1\) or \(d_2\). B: **Incorrect:** Neither \(k_1\) nor \(k_2\) scales with the ambient dimensions \(d_1, d_2\). C: **Incorrect:** Since both datasets have the same number of points \(n\) and the same \(\epsilon\), \(k_1\) and \(k_2\) can be identical. D: **Correct:** The JL target dimension depends only on \(n\) and \(\epsilon\), so \(k_1 = k_2\) is valid.

For two events \(X\) and \(Y\), the logical implication \(X \implies Y\) (if \(X\) occurs, then \(Y\) must also occur) corresponds to the set inclusion: \[X \subseteq Y\] In a Venn diagram, \(X \subseteq Y\) is represented by the circle for event \(X\) lying completely **inside** the circle for event \(Y\), which is shown in **Option C**. **Answer: C (Venn diagram with circle X inside circle Y)** A: **Incorrect:** Disjoint circles represent mutually exclusive events (\(X \cap Y = \emptyset\)). B: **Incorrect:** Circle \(Y\) inside circle \(X\) represents \(Y \subseteq X\) (i.e., \(Y \implies X\)). C: **Correct:** Circle \(X\) completely inside circle \(Y\) represents \(X \subseteq Y\), which means \(X \implies Y\). D: **Incorrect:** Partially overlapping circles allow outcomes in \(X \setminus Y\), violating \(X \implies Y\).

Let \(A\) be a \(d \times n\) random matrix (\(d = 10^4, n = 10^5\)) with i.i.d. \(\mathcal{N}(0, 1)\) entries. When \(n \gg d\), the columns of \(\frac{1}{\sqrt{n}} A^T\) are nearly orthonormal in \(\mathbb{R}^n\), and by concentration of measure (and the Marchenko-Pastur law with aspect ratio \(\gamma = d/n = 0.1\)), all \(10^4\) non-zero singular values of \(A\) concentrate tightly in a narrow band around \(\sqrt{n} \approx 316.2\) (between \(\sqrt{n}(1 - \sqrt{\gamma})\) and \(\sqrt{n}(1 + \sqrt{\gamma})\)). On the full scale of singular values shown in the histograms, this strong concentration around a single value appears as the **tall, narrow spike** in **Option D**. **Answer: D (Histogram with a sharp, narrow peak of singular values)** A: **Incorrect:** Shows a wide bell-shaped spread rather than strong concentration of singular values for \(10^4 \times 10^5\). B: **Incorrect:** Singular values of a rectangular Gaussian matrix are not uniformly distributed. C: **Incorrect:** A bimodal U-shaped (arcsine-like) distribution does not describe the singular values of a Gaussian matrix. D: **Correct:** By concentration of measure for \(10^4 \times 10^5\) i.i.d. Gaussian matrices, the non-zero singular values cluster tightly around \(\sqrt{10^5}\).

**Step 1: Recall the covariance formula for a linear transformation of a random vector.** For \(\omega \sim \mathcal{N}(0, I_2)\), \(\text{Cov}(\omega) = I_2\). Thus, the covariance matrix of \(A\omega\) is: \[\text{Cov}(A\omega) = A\,\text{Cov}(\omega)\,A^T = A I_2 A^T = A A^T\] **Step 2: Compute \(A A^T\) for \(A = \begin{bmatrix} 1 & 4 \\ 3 & 1 \end{bmatrix}\).** \[A A^T = \begin{bmatrix} 1 & 4 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} 1 & 3 \\ 4 & 1 \end{bmatrix} = \begin{bmatrix} 1(1) + 4(4) & 1(3) + 4(1) \\ 3(1) + 1(4) & 3(3) + 1(1) \end{bmatrix} = \begin{bmatrix} 17 & 7 \\ 7 & 10 \end{bmatrix}\] **Answer: A (\(\begin{bmatrix} 17 & 7 \\ 7 & 10 \end{bmatrix}\))** A: **Correct:** \(\text{Cov}(A\omega) = A A^T = \begin{bmatrix} 17 & 7 \\ 7 & 10 \end{bmatrix}\). B: **Incorrect:** \(\begin{bmatrix} 10 & 7 \\ 7 & 17 \end{bmatrix}\) is \(A^T A\) instead of \(A A^T\). C: **Incorrect:** Squares individual entries of \(A\) instead of performing matrix multiplication \(A A^T\). D: **Incorrect:** \(I_2\) is the covariance of \(\omega\), not \(A\omega\).

A Datar-style locality-sensitive hash function for Euclidean space \(h_{a,b} : \mathbb{R}^2 \to \mathbb{Z}\) is defined as: \[h_{a,b}(x) = \left\lfloor \frac{a^T x + b}{w} \right\rfloor\] where \(a \in \mathbb{R}^2\) is a random projection vector, \(b \sim U[0, w]\), and \(w > 0\) is the bucket width. Geometrically, the level sets \(k \le \frac{a^T x + b}{w} < k + 1\) (for \(k \in \mathbb{Z}\)) partition \(\mathbb{R}^2\) into **equally spaced parallel strips bounded by parallel straight lines** perpendicular to \(a\). - **Options A and D** show partitions of \(\mathbb{R}^2\) into equally spaced parallel linear strips (with different random directions \(a\)). - **Options B and C** show concentric circles and ellipses, which cannot be produced by the linear projection \(a^T x + b\). **Answer: A, D** A: **Correct:** Parallel equally-spaced straight lines correspond to a random projection direction \(a\) in Datar LSH. B: **Incorrect:** Concentric circles correspond to a non-linear radial function \(\|x\|\), not \(\lfloor(a^T x + b)/w\rfloor\). C: **Incorrect:** Concentric ellipses correspond to a quadratic form \(x^T M x\), not a linear projection. D: **Correct:** Parallel equally-spaced straight lines at another orientation correspond to another valid random vector \(a\).

In an LSH scheme with \(L\) tables and \(k\) hash functions per table, a collision occurs if two points match in **at least one** of the \(L\) tables: - \(\text{TPR} = 1 - (1 - p_1^k)^L\) - \(\text{FPR} = 1 - (1 - p_2^k)^L\) When we **increase the number of tables \(L\)** while keeping \(k, p_1, p_2\) constant, the quantities \((1 - p_1^k)^L\) and \((1 - p_2^k)^L\) both decrease, which means **both the True Positive Rate (TPR) and the False Positive Rate (FPR) increase**. **Answer: A, B** A: **Correct:** Increasing \(L\) gives more opportunities for true neighbors to collide in at least one table, increasing TPR. B: **Correct:** Increasing \(L\) also gives more opportunities for far points to accidentally collide in at least one table, increasing FPR. C: **Incorrect:** TPR increases (not decreases) as \(L\) increases. D: **Incorrect:** FPR increases (not decreases) as \(L\) increases.

**Step 1: Find the maximum distance between any two points on the unit hypersphere in \(\mathbb{R}^d\).** For any two points \(x, y\) on the unit hypersphere (\(\|x\| = 1\) and \(\|y\| = 1\)), the triangle inequality gives: \[\|x - y\| \le \|x\| + \|y\| = 1 + 1 = 2\] (achieved when \(y = -x\)). **Step 2: Apply the Johnson-Lindenstrauss (JL) distance preservation bound.** Under the JL lemma with parameter \(\epsilon = 0.0201\), the squared distances are preserved within \((1 \pm \epsilon)\): \[\|f(x) - f(y)\|^2 \le (1 + \epsilon)\,\|x - y\|^2 \implies \|f(x) - f(y)\| \le \sqrt{1 + \epsilon}\,\|x - y\|\] Substituting \(\epsilon = 0.0201\) (so \(\sqrt{1 + 0.0201} = \sqrt{1.0201} = 1.01\)) and \(\|x - y\| \le 2\): \[\|f(x) - f(y)\| \le 1.01 \times 2 = 2.02\] **Answer: 2.02**

**Step 1: Recall the Eckart-Young theorem in the spectral (2-norm) norm.** If \(A\) has non-zero singular values \(\sigma_1 \ge \sigma_2 \ge \sigma_3 \ge \sigma_4 \ge \sigma_5 \ge \sigma_6\) and \(B\) is the best rank-\(k\) approximation of \(A\), then the spectral norm error is the \((k+1)\)-th singular value: \[\|A - B\|_2 = \sigma_{k+1}\] **Step 2: Identify \(\sigma_5\) for \(k = 4\).** The given singular values in decreasing order are: \[\sigma_1 = 50, \quad \sigma_2 = 20, \quad \sigma_3 = 10, \quad \sigma_4 = 1, \quad \sigma_5 = 0.01, \quad \sigma_6 = 0.001\] For \(k = 4\), \(\|A - B\|_2 = \sigma_5 = 0.01\). **Answer: 0.01**

**Step 1: Express the cut weight for a singleton set \(A = \{v\}\) with \(|A| = 1\).** For any single vertex \(v \in \{1, 2, 3, 4, 5, 6\}\), the cut \((A, V \setminus A)\) consists of all edges incident to \(v\), so its cumulative sum of weights is simply the **weighted degree** \(d_v\) of vertex \(v\). **Step 2: Compute the weighted degree of each vertex from the given graph.** - Vertex 1: connected to 2 (weight 1) and 3 (weight 2) \(\implies d_1 = 1 + 2 = 3\). - Vertex 2: connected to 1 (weight 1) and 3 (weight 3) \(\implies d_2 = 1 + 3 = 4\). - Vertex 3: connected to 1 (weight 2) and 2 (weight 3) \(\implies d_3 = 2 + 3 = 5\). - Vertex 4: connected to 5 (weight 1) and 6 (weight 2) \(\implies d_4 = 1 + 2 = 3\). - Vertex 5: connected to 4 (weight 1) and 6 (weight 3) \(\implies d_5 = 1 + 3 = 4\). - Vertex 6: connected to 4 (weight 2) and 5 (weight 3) \(\implies d_6 = 2 + 3 = 5\). The minimum cut weight among all \(|A| = 1\) cuts is \(\min(3, 4, 5, 3, 4, 5) = 3\) (achieved by \(A = \{1\}\) or \(A = \{4\}\)). **Answer: 3**

**Step 1: Recall the definition of the Graph Laplacian \(L = D - W\).** - The diagonal entries \(L_{ii} = d_i\) are the weighted degrees of the vertices: \(d_1 = 3, d_2 = 4, d_3 = 5, d_4 = 3, d_5 = 4, d_6 = 5\). - The off-diagonal entries are \(L_{ij} = -w_{ij}\) if there is an edge between \(i\) and \(j\), and \(0\) otherwise. **Step 2: Construct \(L\).** Since vertices \(\{1, 2, 3\}\) and \(\{4, 5, 6\}\) form two identical disconnected triangles with edge weights \(w_{12}=w_{45}=1\), \(w_{13}=w_{46}=2\), and \(w_{23}=w_{56}=3\): \[L = \begin{bmatrix} 3 & -1 & -2 & 0 & 0 & 0 \\ -1 & 4 & -3 & 0 & 0 & 0 \\ -2 & -3 & 5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & -1 & -2 \\ 0 & 0 & 0 & -1 & 4 & -3 \\ 0 & 0 & 0 & -2 & -3 & 5 \end{bmatrix}\] **Answer: A** A: **Correct:** \(L = D - W\) has the weighted degrees \((3, 4, 5, 3, 4, 5)\) on the diagonal and negative edge weights off the diagonal. B: **Incorrect:** Sets all diagonal entries to 0 (giving \(-W\) instead of \(D - W\)). C: **Incorrect:** Uses \(W - D = -L\) with negative diagonal entries. D: **Incorrect:** Uses positive off-diagonal weights and incorrect diagonal degrees.

**Step 1: Recall the spectral property of the Graph Laplacian \(L\).** For any undirected graph with non-negative edge weights, the multiplicity of \(0\) as an eigenvalue of the Laplacian matrix \(L\) is equal to the **number of connected components** of the graph. **Step 2: Count the connected components.** The graph consists of two disconnected triangles: \(\{1, 2, 3\}\) and \(\{4, 5, 6\}\). Since there are **2** connected components, \(L\) has exactly **2** zero eigenvalues. **Answer: 2**