Making a matrix as sparse as possible
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Consider a matrix $A in mathbbR^m times n$ where $n >> m$. In other words, $A$ has much more columns than rows. Also, consider we are given a fixed number (integer) $m leq r < n$. I'm trying to find a matrix $B in mathbbR^r times m$ such that $B' B = I_m$ (i.e., $B'$ is the left inverse of $B$) and $BA$ is very sparse, as much as possible.
My first idea was to consider the case $r = m$ and take the $QR$ factorization of $A$. Then set $B = Q^T$ to get
$$BA = Q^TA = Q^TQR = I_mR = R,$$
a triangular (and rectangular) matrix. This matrix has a few zeros in the first $m$ columns, but since $m$ is much smaller than $n$, there are a lot of non zero terms left. Also, in my context usually $r$ will be bigger than $m$ and smaller than $n$, so I don't want to choose specif values for $r$. I really want a general approach that maximizes the number of zero entries in $BA$ for a generic $r$ between $m$ and $n$.
I wonder if there is a better matrix to do the job. Hope you can help me.
Thank you.
linear-algebra matrices linear-transformations sparse-matrices
asked Aug 25 at 1:17
Integral
3,83111640
add a comment |Â
up vote
2
down vote
favorite
Consider a matrix $A in mathbbR^m times n$ where $n >> m$. In other words, $A$ has much more columns than rows. Also, consider we are given a fixed number (integer) $m leq r < n$. I'm trying to find a matrix $B in mathbbR^r times m$ such that $B' B = I_m$ (i.e., $B'$ is the left inverse of $B$) and $BA$ is very sparse, as much as possible.
My first idea was to consider the case $r = m$ and take the $QR$ factorization of $A$. Then set $B = Q^T$ to get
$$BA = Q^TA = Q^TQR = I_mR = R,$$
a triangular (and rectangular) matrix. This matrix has a few zeros in the first $m$ columns, but since $m$ is much smaller than $n$, there are a lot of non zero terms left. Also, in my context usually $r$ will be bigger than $m$ and smaller than $n$, so I don't want to choose specif values for $r$. I really want a general approach that maximizes the number of zero entries in $BA$ for a generic $r$ between $m$ and $n$.
I wonder if there is a better matrix to do the job. Hope you can help me.
Thank you.
linear-algebra matrices linear-transformations sparse-matrices
asked Aug 25 at 1:17
Integral
3,83111640
You might start by trying to solve the simpler problem: Let $A in mathbbR^m times n$, with $m < n$. What is $mathrmargmin_B in mathbbR^r times m, mathbfrank(B) geq m mathrmnnz(BA)$?
– Drew Brady
Aug 25 at 9:06
@DrewBrady Is this a rethorical question? I don't know what is this argmin. Furthermore, I think the condition $B^TB = I_m$ automatically implies $rank(B) = m$, which is the maximal possible rank attainable.
– Integral
Aug 25 at 14:53
Looks like you just rephrased my question. I can't see how simpler is your formulation.
– Integral
Aug 25 at 14:56
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Consider a matrix $A in mathbbR^m times n$ where $n >> m$. In other words, $A$ has much more columns than rows. Also, consider we are given a fixed number (integer) $m leq r < n$. I'm trying to find a matrix $B in mathbbR^r times m$ such that $B' B = I_m$ (i.e., $B'$ is the left inverse of $B$) and $BA$ is very sparse, as much as possible.
My first idea was to consider the case $r = m$ and take the $QR$ factorization of $A$. Then set $B = Q^T$ to get
$$BA = Q^TA = Q^TQR = I_mR = R,$$
a triangular (and rectangular) matrix. This matrix has a few zeros in the first $m$ columns, but since $m$ is much smaller than $n$, there are a lot of non zero terms left. Also, in my context usually $r$ will be bigger than $m$ and smaller than $n$, so I don't want to choose specif values for $r$. I really want a general approach that maximizes the number of zero entries in $BA$ for a generic $r$ between $m$ and $n$.
I wonder if there is a better matrix to do the job. Hope you can help me.
Thank you.
linear-algebra matrices linear-transformations sparse-matrices
asked Aug 25 at 1:17
Integral
3,83111640
Consider a matrix $A in mathbbR^m times n$ where $n >> m$. In other words, $A$ has much more columns than rows. Also, consider we are given a fixed number (integer) $m leq r < n$. I'm trying to find a matrix $B in mathbbR^r times m$ such that $B' B = I_m$ (i.e., $B'$ is the left inverse of $B$) and $BA$ is very sparse, as much as possible.
My first idea was to consider the case $r = m$ and take the $QR$ factorization of $A$. Then set $B = Q^T$ to get
$$BA = Q^TA = Q^TQR = I_mR = R,$$
a triangular (and rectangular) matrix. This matrix has a few zeros in the first $m$ columns, but since $m$ is much smaller than $n$, there are a lot of non zero terms left. Also, in my context usually $r$ will be bigger than $m$ and smaller than $n$, so I don't want to choose specif values for $r$. I really want a general approach that maximizes the number of zero entries in $BA$ for a generic $r$ between $m$ and $n$.
I wonder if there is a better matrix to do the job. Hope you can help me.
Thank you.
linear-algebra matrices linear-transformations sparse-matrices
asked Aug 25 at 1:17
Integral
3,83111640
edited Aug 25 at 15:32
asked Aug 25 at 1:17
Integral
3,83111640
asked Aug 25 at 1:17
Integral
3,83111640
asked Aug 25 at 1:17
Integral
3,83111640
3,83111640
You might start by trying to solve the simpler problem: Let $A in mathbbR^m times n$, with $m < n$. What is $mathrmargmin_B in mathbbR^r times m, mathbfrank(B) geq m mathrmnnz(BA)$?
– Drew Brady
Aug 25 at 9:06
@DrewBrady Is this a rethorical question? I don't know what is this argmin. Furthermore, I think the condition $B^TB = I_m$ automatically implies $rank(B) = m$, which is the maximal possible rank attainable.
– Integral
Aug 25 at 14:53
Looks like you just rephrased my question. I can't see how simpler is your formulation.
– Integral
Aug 25 at 14:56
add a comment |Â
You might start by trying to solve the simpler problem: Let $A in mathbbR^m times n$, with $m < n$. What is $mathrmargmin_B in mathbbR^r times m, mathbfrank(B) geq m mathrmnnz(BA)$?
– Drew Brady
Aug 25 at 9:06
@DrewBrady Is this a rethorical question? I don't know what is this argmin. Furthermore, I think the condition $B^TB = I_m$ automatically implies $rank(B) = m$, which is the maximal possible rank attainable.
– Integral
Aug 25 at 14:53
Looks like you just rephrased my question. I can't see how simpler is your formulation.
– Integral
Aug 25 at 14:56
You might start by trying to solve the simpler problem: Let $A in mathbbR^m times n$, with $m < n$. What is $mathrmargmin_B in mathbbR^r times m, mathbfrank(B) geq m mathrmnnz(BA)$?
– Drew Brady
Aug 25 at 9:06
You might start by trying to solve the simpler problem: Let $A in mathbbR^m times n$, with $m < n$. What is $mathrmargmin_B in mathbbR^r times m, mathbfrank(B) geq m mathrmnnz(BA)$?
– Drew Brady
Aug 25 at 9:06
@DrewBrady Is this a rethorical question? I don't know what is this argmin. Furthermore, I think the condition $B^TB = I_m$ automatically implies $rank(B) = m$, which is the maximal possible rank attainable.
– Integral
Aug 25 at 14:53
@DrewBrady Is this a rethorical question? I don't know what is this argmin. Furthermore, I think the condition $B^TB = I_m$ automatically implies $rank(B) = m$, which is the maximal possible rank attainable.
– Integral
Aug 25 at 14:53
Looks like you just rephrased my question. I can't see how simpler is your formulation.
– Integral
Aug 25 at 14:56
Looks like you just rephrased my question. I can't see how simpler is your formulation.
– Integral
Aug 25 at 14:56
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2893725%2fmaking-a-matrix-as-sparse-as-possible%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
You might start by trying to solve the simpler problem: Let $A in mathbbR^m times n$, with $m < n$. What is $mathrmargmin_B in mathbbR^r times m, mathbfrank(B) geq m mathrmnnz(BA)$?
– Drew Brady
Aug 25 at 9:06
@DrewBrady Is this a rethorical question? I don't know what is this argmin. Furthermore, I think the condition $B^TB = I_m$ automatically implies $rank(B) = m$, which is the maximal possible rank attainable.
– Integral
Aug 25 at 14:53
Looks like you just rephrased my question. I can't see how simpler is your formulation.
– Integral
Aug 25 at 14:56