0
$\begingroup$

I am trying to understand A Fast Random Sampling Algorithm for Sparsifying Matrices (Arora, Hazan, Kale).

I don’t understand the meaning of the notation: $$\Vert A \Vert_2 = \max_{\Vert x \Vert_2 = 1} \left\vert Ax \right\vert$$

Could somebody explain it please?

EDIT Follow up questions:

Why is the norm of the matrix $A$ defined as $\max |Ax|$. Is $x$ any vector in the column space of $A$?

I understand the arithmetic max operator, which returns the maximum of two quantities, but here, I see just one quantity $|Ax|$. Is that a determinant?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

$||.||_2$ denotes a norm defined for matrices by $||A||_2 = \max_{|x|=1}|Ax|$. It is defined in this way so the following equality holds true $$|Ax|\leq||A||_2 |x|.$$

You can read more about it on http://en.wikipedia.org/wiki/Operator_norm.

$\endgroup$
4
  • $\begingroup$ Ah.. I see. thanks $\endgroup$
    – frazman
    Commented Aug 14, 2014 at 4:00
  • $\begingroup$ do you know why the norm of matrix A is max |Ax|.. is x any vector in A column space? I know the arithmetic max operator.. which returns max between two quantities.. but here, I see just just one quantity |Ax|?? Is that a determinant? Sorry for asking so many trivial questions? $\endgroup$
    – frazman
    Commented Aug 14, 2014 at 4:05
  • $\begingroup$ These are good questions. The norm $||A||_2$ of the matrix $A$ is defined to be the maximum of all numbers $|Ax|$, where $x$ ranges over unit vectors, that is, vectors who have length $1$. $Ax$ simply denotes the multiplication of the vector $x$ with the matrix $A$. The result will be a vector and $|Ax|$ is just the norm of this resulting vector. $\endgroup$
    – rehband
    Commented Aug 14, 2014 at 8:40
  • $\begingroup$ Observe that this definition yields the inequality $|Ax| \leq ||A||_2 |x|$ for all vectors $x$, as I have said before in my answer. :) $\endgroup$
    – rehband
    Commented Aug 14, 2014 at 8:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .