Dear Alex, Try playing with the mutual information/conditional entropy decomposition of the mapping F. The best, Bob

Dear Researcher, in this case you have to first determine the complexities of the individual composition functions and from that you can derive a some kind of recurrence relation (or so) to approximate the overall complexity of your original function. It will be better if you can provide an example function and its decompositions in component functions.

I'm not sure that your attempted defined property of higher complexity always holds. I believe that If the complexity of F is similar to that of f1, and the complexity of f1 is very large compared to that of f2, then the addition of the complexities of f1, f2 and "+" not necessarily is (significantly) smaller to that of F.

Dear Bob,

Thanks for advice! I was trying to find some solution not involving these notions, but if you won't do, I will have to look there.

Alex

Dear Juan,

The definition of complexity I am trying to find or build up is mainly based on the dimensionality of the involved components. In this sense, the complexity of F is higher than that of f1 because F maps Rm->Rn and f1 maps Rk->Rn, k < m. In this way the complexity of a linear function R1->R1 could be the same as the complexity of any other R1->R1 function.

But I have only some intuition about the properties I need. I do not intend to build this definition myself, I would rather prefer to find something matching my needs. And the needs are to be able to characterize the complexity of mapping representation.

Best,

Alex

Dear Ratnadip,

Thank you, that is exactly the way I would proceed. However I would prefer to find a ready-made definition and a theory around it.

Best,

Alex

Dear Alex,

If F or f1 and f2 bare a differential structure, then, since metric |(dx1,...,dxn)|^2 should be retained for both representations, if F=f1+f2 then, I think, the Jacobians of f1 and f2 should satisfy df1*transpose(df2)=0. Thus, a Lagrangian of the form |f1+f2-f|^2 + q*norm(df1*transpose(df2)) should fit the problem of determining such a decomposition for F.

Concerning the dimensionality of the decomposition, eq. df1*transpose(df2)=0 requires for 2 orthogonal n-dimensional vector spaces one of rank up to 'k' and one of rank up to 'm-k'. Then, the rank of the Jacobian of F is identified by the sum of these two ranks.

Dear Dimitris,

Thank you very much for your response. Indeed, it's a good idea to look at metrics. But it seems that this would not hold if it was an element-wise multiplication used instead. Do you have any ideas about a more general approach?

Best,

Alex

Dear Alex,

If I understand well the generalization you refer to, you seek for a decomposition F in the form F=P(f1,f2), where P an arbitrary map

R^n x R^n --> R^n. If P bares 1st order differentials, then, for M1=dP/df1 and M2=dP/df2, the condition of preserving

|(dx1,...,dxn)|^2 for F and P(f1,f2), is interpreted as df1*M1*transpose(df2*M2)=0.

The dimensionality of the decomposition does not change regarding its upper value, since both M1 and M2 have ranks up to n>m,k. Concerning the rank of the Jacobian of F is identified by rank(df1*M1)+rank(df2*M2).

Best regards,

Dimitris

Dear Aleix

according to the best of my knowledge , the complexity is the time needed to perform

some given algorithm which depends on the nature of the input function (or data),

in this approach you need to restate your question so one can help .

regards

Dear Issam,

Thank you for your answer. I am looking for the definition of complexity that would not depend on the choice of elementary functions. Correct me if I'm wrong but it seems to me that when there are algorithms involved the time required to evaluate a function depends on the elementary functions assumed in the algorithm.

Best,

Alex

Dear Dimitris,

Thank for your answers. I fact I understood that I don't understand what you suggest. By preserving ||dx|| do you mean preserving ||dF|| = ||DF/Dx dx||? Here DF/Dx is a Jacobean of F. Otherwise I don't understand, because ||dx|| is an independent variable here. And could you explain where the condition df1*M1 (df2*M2)^T comes from?

Best,

Alex

Dear Alex,

from the statement of the question "x" is the target and not the independent variable as it results from mapping an (independent) variable "y" by "F": x = F(y).

So preserving ||dx||^2 equates || (DF/Dy)^T dy ||^2 with ||(Df1/Dy + Df2/Dy) dy ||^2.

Expanding the second expression for ||dx||^2 and using both arbitrariness of "dy" (I supposed it is the independent variable ) and symmetry of DF/Dy * (DF/Dy)^T, df1*M1*(df2*M2)^T results .

Concerning the symmetry of DF/Dy * (DF/Dy)^T, it can be shown by writting F(y)=[a1(y),...,an(y)]^T and DF/Dy=[Da1/Dy,...,Dan/Dy].

Best,

Dimitris

Dear Dimitris,

Thank you so much for spending your time on my problem. I am sorry, but I still do not understand.

The problem:

x = F(y) = f1(y) + f2(y)

As you've correctly noticed, ||dx|| does not depend on the representation of the mapping. Hence

||DF/Dy dy|| = ||(Df1/Dy + Df2/Dy) dy||.

As it holds for all possible dy

DF/Dy = Df1/Dy + Df2/Dy.

I don't understand the manipulations you perform next. Would you be so kind to give some explanations.

Thanks in advance!

Best,

Alex

Dear Alex,

Please ignore this pdf as it has some inconsistencies.

I'll upload one with the manipulation for the vanishing df1*M1*(df2*M2)^T the next days.

Best,

Dimitris.

Dear Alex,

Please find attached the pdf with the entire manipulation.

Please inform me for any obscure or inconsistent points, as I used to employ such a decomposition somewhat long ago.

Best,

Dimitris

Dear Dimitris,

Thank you so much! I skimmed it over and the first impression is that it is understandable. I will read it more carefully and come back to you later.

BTW, could you point to some papers of yours relevant to this issue.

Best,

Alex

Dear Alex,

did you find a measure? If not I would suggest Big O Notation, which has a rich theory. Consider that the mapping between functions is list sorting. You could either use merge sort, which is O(n log(n)) or bubble sort, which is O(n^2). Merge sort needs fewer steps, so in this sense a decomposition has taken place. I'm not sure how this can be related to the linear decomposition you are asking for.

Big O Notation comes from complexity theory where problems define different complexity classes. You would try to show, that F is in a different complexity class ( e.g. O(n^n)), than F1 + F2, say (e.g. O(n^2 + n ^2) = O(n^2)).

Best,

Johannes