TIFR CSE 2010 | Part A | Question: 11

Question

The length of a vector $X = (x_{1},\ldots,x_{n})$ is defined as

$$\left \|  X\right \| = \sqrt{\sum \limits^{n}_{i=1}x^{2}_{i}}$$

Given two vectors $X=(x_{1},\ldots, x_{n})$ and $Y=(y_{1},\ldots, y_{n})$, which of the following measures of discrepancy between $X$ and $Y$ is insensitive to the length of the vectors?

• A. $\left \| X - Y \right \|$
• B. $\left \| X - Y \right \|/\left \| x \right \|\left \| y \right \|$
• C. $\left \| X \right \|-\left \| Y \right \|$
• D. $\left \| \frac{X}{\left \| X \right \|}-\frac{Y}{\left \| Y \right \|} \right \|$
• E. None of the above

Comments

What will be the answer if the question changes from insensitive to sensitive to the length of vectors?

somebody give better explanations...

Answer 1

Option D is the correct answer.

The following statement

discrepancy between x and y is insensitive to the length of the vectors

means that The discrepancy, as measured by the formula, between two vectors $x$ and $y$ is same as the discrepancy between the vectors $c_1 x$ and $c_2 y$, for any constant scalars $c_1, c_2$. That is,

$D(x,y) = D(c_1 x, c_2 y), \quad \forall c_1, c_2 \in \mathbb{R}$

Now, lets think about which formula achieves that.

Let us also define two pairs of vectors as follows:

$x_1 = (0.1067, 0.9619, 0.0046, 0.7749, 0.8173)$

$ y_1 = (0.8687, 0.0844, 0.3998, 0.2599, 0.8001)$

$x_2 = 0.4314 \times x_1 = (0.0460, 0.4150, 0.0020, 0.3343, 0.3526)$

$y_2 = 0.9106 \times y_1 = (0.7911, 0.0769, 0.3641, 0.2367, 0.7286)$

---

A) $\| x - y \|$

Since the definition of $\| x \|$ is sensitive to scaling, option A won't be insensitive to scaling either.

For example, 

$D(x_1,y_1) = \| x_1 - y_1 \| \approx 1.3313$

$D(x_2,y_2) = \| x_2 - y_2 \| \approx 0.9754$

$D(x_1,y_1) \neq D(x_2,y_2)$

---

B) $\frac{\| x-y \|}{\|x\| \|y\|}$

Once we've subtracted the vectors, scaling them according to their original lengths won't help at all.

For example,

$D(x_1,y_1) = \frac{\| x_1-y_1 \|}{\|x_1\| \|y_1\|} \approx 0.7024$

$D(x_2,y_2) = \frac{\| x_2-y_2 \|}{\|x_2\| \|y_2\|} \approx 1.3099$

$D(x_1,y_1) \neq D(x_2,y_2)$

---

C) $\|x\| - \|y\|$

We aren't doing any scaling in this definition of discrepancy. So, this definition is certainly sensitive to scaling, and thus, not the correct answer.

For example,

$D(x_1,y_1) = \|x_1\| - \|y_1\| \approx 0.2086$

$D(x_2,y_2) = \|x_2\| - \|y_2\| \approx -0.5217$

$D(x_1,y_1) \neq D(x_2,y_2)$

---

D) $\left \| \frac{x}{\|x\|}-\frac{y}{\|y\|} \right \|$

In this, we first scale each vector $x$ and $y$ down to their unit vectors, and then calculate the discrepancy.

Since $x_2 = c_1 x_1$, $x_2$ will have the same unit vector as $x_1$.
Similarly, $y_2$ will have the same unit vector as $y_1$.

Thus, no matter how we scale $x_2$ and $y_2$, as long as they are derived from $x_1$ and $y_1$, their discrepancy will be the same.

Therefore, our formula will be insensitive to scaling, which is exactly what we want!

For example,

$D(x_1,y_1) = \left \| \frac{x_1}{\|x_1\|}-\frac{y_1}{\|y_1\|} \right \| \approx 0.9551$

$D(x_2,y_2) = \left \| \frac{x_2}{\|x_2\|}-\frac{y_2}{\|y_2\|} \right \| \approx 0.9551$

$D(x_1,y_1) = D(x_2,y_2)$

---

Thus, option D is the correct answer.

You can use this matlab code to test the options with randomly generated vectors.

%% Get two random vectors x1 and y1, each of length 5 
x1 = rand(5,1); 
y1 = rand(5,1);

%% Create two more vectors x2 and y2, which are multiples of x1 and y1
x2 = rand()*x1;
y2 = rand()*y1;

%% Define the modd function
modd = @(z) sqrt(sum(z.^2));

%% Define the answers function that computes the values
%  obtained from options A, B, C and D
answers = @(x,y) [
                modd(x-y);
                modd(x-y)/(modd(x)*modd(y));
                modd(x) - modd(y);
                modd(x/modd(x)  - y/modd(y))
            ];

%% Define function to perform floating point comparision
%  Copied from stackoverflow.com/a/2203483/2570622
isequalRel = @(x,y,tol) ( abs(x-y) <= ( tol*max(abs(x),abs(y)) + eps) );

%% Calculate the answers for (x1, y1) and (x2, y2) and see which option
%  remains unaffected.
isequalRel(answers(x1,y1), answers(x2,y2), 1e-6)

Comments

Plz chk with some -ve values

I am getting option D) is not giving correct option in that case

Suppose $x=< 2,-1>$  and $y=< 4,6>$

I am getting D) false

Plz correct me if wrong

---

option (D) is the  subtraction of unit vectors of both vectors $X$ and $Y$.

By definition, unit vectors only express direction, and no magnitude (which indicates the length in this case), hence they're basically independent of magnitude, hence, we cannot find magnitude from unit vectors, it's the only correct choice.