3
$\begingroup$

I apologize if this is a naive question. I'm trying to create some boostrap data for a system of linear, ordinary differential equations at steady state.

Since the equations represent the concentration of chemical species, X has to be positive. Further, I'm trying to find the sparsest possible matrix of A, for the sake of keeping the dependency graph of the equations as small as possible.

Using the cvx toolbox in MATLAB, I put the problem like this:

clear

% the threshold value below which we consider an element to be zero
delta = 1e-8;

% problem dimensions (m inequalities in n-dimensional space)
n = 25;

X  = rand(n, 1)
b  = zeros(n, 1);
c = zeros(n, n) + delta^2
alpha = 0.1


% l1-norm heuristic for finding a sparse solution
fprintf(1, 'Finding a sparse feasible point using l1-norm heuristic ...')
cvx_begin
  variable A(n,n) 
  %minimize(nnz(A))
  minimize(alpha * nnz( A ) + (1-alpha) * norm(A*X - b, 2) )
cvx_end

% number of nonzero elements in the solution (its cardinality or diversity)
nonzero = length(find( abs(A) > delta ));
fprintf(1,['\nFound a feasible A in R^%d that has %d nonzeros ' ...
           'using the l1-norm heuristic.\n'],n,nonzero);    

This tends to find matrix of A which are filled with incredibly small near zero values. Does anyone have suggestions for heuristic approaches to find a combination of X and A which satisfy the constraints I described above? They don't need to be particularly fast or memory efficient, I'm working with relatively small matrix.

To be clear - I'm not trying to solve for a particular A or X. I'm trying to find a combination of A and X that satisfy the constraints I described.

$\endgroup$
  • $\begingroup$ When you say "incredibly small near zero": how bad would the results be if you just rounded those down to zero? CVX solvers do not snap to a solution vertex, so that means you're never going to get identically zero results. $\endgroup$ – Michael Grant Apr 8 '13 at 16:09
  • $\begingroup$ Sorry, I should have been more clear. I mean that I'm not looking for trivial solutions where A is a matrix full of 0s. $\endgroup$ – Fede_v Apr 8 '13 at 17:29
  • $\begingroup$ Actually I see one problem: nnz(A) is probably not doing what you think. With CVX variables, it returns the number of structural nonzeros. It's a constant, not a function, in this context. $\endgroup$ – Michael Grant Apr 8 '13 at 18:05
  • $\begingroup$ Your title and code is confusing, since you talk about a positive non-zero B, but in the beginning of the title, and in the code, you use a zero b, which makes the problem trivial (A=0 is optimal). $\endgroup$ – Johan Löfberg Apr 8 '13 at 18:30
  • $\begingroup$ I actually screwed up editing the title. I meant to say positive, non-zero X, and sparse A. Apologies. $\endgroup$ – Fede_v Apr 8 '13 at 18:40
2
$\begingroup$

Without loss of generality we may treat the case $X$ is all-ones vector $u$, since forming $AD^{-1}X$ is equivalent to $Au$ where $D = \text{diag}(X)$ is the diagonal matrix with entries from $X$, and $A$ has the same sparsity as $AD^{-1}$.

Mention is made of "keeping the dependency graph of the equations as small as possible". Aside from avoiding the triviality of a matrix of all zeros, one might want to impose a condition that this dependency graph be connected, or more weakly, that no row of $A$ is allowed to be all zeros.

If the goal is to minimize the number of nonzero entries in $A$, subject to $Au=0$, then we must have at least two nonzero entries in each nonzero row of $A$. Moreover this minimum can be attained by placing both a $+1$ and a $-1$ entry in each such row.

If connectedness of the dependency graph is sought, it can be achieved without further loss of sparsity. For example, define $A = I - P$ where $P$ is the permutation matrix s.t. $P_{1,n} = 1$, $P_{i+1,i} = 1$ for $i=1,\ldots,n-1$, and otherwise $P_{i,j} = 0$.

$\endgroup$
  • $\begingroup$ Hardmath - thank you very much for the reply. The suggestion about connectedness is also very helpful. I am however still not very sure about how you'd go about generating A and X - if it isn't too much trouble, could you give me a hint with some pseudo code for a case where X is not a vector of all 1s? – Fede_v 45 mins ago $\endgroup$ – Fede_v Apr 9 '13 at 19:03
  • $\begingroup$ What I said was that if $X$ is strictly positive (my interpretation of what you posed), then solving for $A$ in the general case is easily referred to the solutions for vector $X = u$ of all-ones. Right? You just throw in the diagonal factor $D^{-1}$ for a general positive $X$, so $AD^{-1}X = Au$ when $D = \text{diag}(X)$. [You seem familiar with Matlab syntax.] $\endgroup$ – hardmath Apr 9 '13 at 19:30
3
$\begingroup$

You talk about l1-heuristics, but in the code it looks more like you are interested in solving the underlying combinatorial problem involving the nnz of A. In a l1-heuristics, you would typically use norm(A(:),1) or something like that. The fact you only get zeros is natural as the problem is homogenous in A when b is 0. You can introduce an arbitrary scale in the problem though, such as sum(sum(A))=1 to ensure the solution is non-zero.

$\endgroup$
  • 1
    $\begingroup$ Yes. In fact, nnz(A) is not a valid function, combinatorial or otherwise, in CVX. I mean, it returns a result, but it's a constant value equal to the number of structural nonzeros. I should probably remove it, frankly, to prevent this kind of confusion. $\endgroup$ – Michael Grant Apr 8 '13 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.